Петя разрабатывает компьютерную игру. Игровое поле состоит из 11 островов, обозначенных латинскими буквами от A до K. На острове A стоит замок Героя. Некоторые острова соединены мостами. В рамках одного из заданий Герой должен обойти часть (возможно все) острова и собрать дань с их жителей. При этом, если Герой проходит по мосту, соединяющему два острова, мост рушится и больше по нему пройти нельзя. Задание считается выполненным только, если Герой возвращается на остров со своим замком. Информацию об игровом поле Петя хранит в базе данных, содержащей, в частности, две таблицы: Острова и Мосты. Каждая запись в таблице «Острова» хранит сведения об уникальном идентификаторе записи, названии острова и объеме дани, которую можно собрать с его жителей. Каждая запись таблицы «Мосты» хранит сведения об уникальном идентификаторе записи и двух идентификаторах островов, если между этими островами есть мост.
Петя посмотрел на текущие записи в таблицах:
Острова |
ID |
Название |
Дань |
1 |
A |
0 |
2 |
B |
20 |
3 |
C |
10 |
4 |
D |
20 |
5 |
E |
70 |
6 |
F |
10 |
7 |
G |
20 |
8 |
H |
30 |
9 |
I |
30 |
10 |
J |
50 |
11 |
K |
30 |
Мосты |
ID |
ID острова 1 |
ID острова 2 |
1 |
1 |
7 |
2 |
1 |
11 |
3 |
2 |
4 |
4 |
3 |
10 |
5 |
4 |
6 |
6 |
4 |
11 |
7 |
5 |
7 |
8 |
7 |
10 |
9 |
8 |
10 |
10 |
9 |
11 |
Проанализировав записи, Петя понял, что Герой не сможет выполнить задание. Тогда он добавил Герою возможность в рамках выполнения задания построить один новый мост, связав любые два острова. Определите, какой мост нужно построить, чтобы в результате Герой выполнил задание и при этом собрал максимальную дань. В ответе укажите подряд без пробелов сначала два символа, обозначающие названия островов, которые свяжет новый мост (отсортировав их по возрастанию), а затем число – дань, которую соберет Герой, выполнив задание.