Each fighter of the 25th Rifle Division has been given the newest communication
device—a mobile telegraph. It can be used for sending telegrams to the command
and to fellow fighters right at the battle field. Unfortunately, the design of
telegraphs is still far from being perfect, so messages can be sent only
between some pairs of telegraphs.
Each device has a unique number, which is a string consisting of ten decimal digits.
A message can be sent from a telegraph a to a telegraph b only if the number b
can be obtained from the number a by changing exactly one digit or by swapping two
digits, and the time of sending a message from the telegraph a to the telegraph b
depends on the length of the longest common prefix of their numbers: the longer
the common prefix is, the faster the message is sent.
During a battle, Anka noticed from her well-camouflaged position the group of Whites
trying to bypass Red Army fighters in the rear. What minimal time is required
to deliver this information from Anka to Chapaev by telegraph, using, possibly,
telegraphs of other Red Army fighters?
The first line contains the number n of fighters in the division
(2 ≤ n ≤ 50000). The second line contains ten integers in the range
from 1 to 10000 separated with a space written in the nonascending order.
These are the times of sending a message from one telegraph to another if the
length of their common prefix is zero, one, two, …, nine. The next n
lines contain the numbers of telegraphs given to the fighters of the division.
The number of Anka's telegraph is described first, and the number of Chapaev's
telegraph is described last. All the numbers of telegraphs are different.
Output the only line “-1” if it is impossible to deliver the message to Chapaev.
Otherwise, in the first line output the minimal time required to deliver the message.
In the second line output the number of fighters in the delivery path,
and in the third line output their numbers separated with a space in the
order from Anka to Chapaev. The fighters of the 25th Division are numbered
from 1 to n in the order in which their mobile telegraphs are described in
the input. If there are several ways to deliver the message in minimal
time, output any of them.
100 10 10 10 1 1 1 1 1 1
1 2 4 3 5
1 1 1 1 1 1 1 1 1 1
Problem Author: Pavel Atnashev
Problem Source: NEERC 2010, Eastern subregional contest