시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые c цифр телефонов совпадают, а (c + 1)-я цифра различается, то стоимость сообщения составляет (10 – c) кредитов (0 ≤ c ≤ 9). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время –2 часа от московского) своему учителю — профессору де Кодеру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время –1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Кодеру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

Напишите программу, определяющую цепочку доставки, для которой суммарная стоимость отправленных сообщений минимальна.

입력

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Кодера. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число ni (1 ≤ ni ≤ 100 000) — количество друзей Поликарпа в соответствующем городе, после которой следуют ni строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех ni не превосходит 100 000. Все номера телефонов во входных данных различны.

출력

В первой строке выходного файла выведите минимальную возможную стоимость передачи информации w и количество задействованных в цепочке телефонных номеров k. Далее выведите k номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Кодеру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Кодера. Если решений несколько, выведите любое.

예제 입력 1

1000000000
5000000000
1
9999999999
1
2000000000
1
3000000000
1
4000000000
1
8888888888

예제 출력 1

40 5
1000000000
2000000000
3000000000
4000000000
5000000000

예제 입력 2

2358847598
0023483473
1
0454385729
2
2358847500
2358840000
2
2358840001
2358847501
1
2358840002
1
0023483471

예제 출력 2

16 5
2358847598
2358840000
2358840001
2358840002
0023483473