ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2010, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Mobile Telegraphs

Time limit: 3.0 second
Memory limit: 256 MB
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
To submit the solution for this problem go to the Problem set: 1806. Mobile Telegraphs