Ломоносов отбор 3

/*Сдать решение задачи 3-1011-Сундуки
Полный балл:  1
Имя входного файла: input.txt или стандартный поток ввода
Ограничение времени:  1 с
Ограничение реального времени:   5 с
Ограничение памяти:    512M
Сундуки. 10-11 класс
Скупой рыцарь хранит в подвале множество сундуков. Сундуки занумерованы, начиная с единицы. В сундуках лежат монеты и банкноты. О содержимом каждого сундука есть опись. В описи строчными латинскими буквами обозначаются монеты: a -- монета номиналом 1 копейка; b -- 5 копеек; с -- 10 копеек; d -- 50 копеек; e -- 1 рубль или 100 копеек; f -- 2 рубля; g -- 5 рублей; h -- 10 рублей; i -- 25 рублей. В описи заглавными латинскими буквами обозначаются банкноты: A -- банкнота номиналом 5 рублей; B -- банкнота номиналом 10 рублей; C -- 50 рублей; D -- 100 рублей; E -- 200 рублей; F -- 500 рублей; G -- 1000 рублей; H -- 2000 рублей; I -- 5000 рублей. Другие символы в описях не используются. Буква входит в опись столько раз, сколько монет или банкнот соответствующего номинала лежит в сундуке. Буквы в описи могут идти в произвольном порядке, так как скупой рыцарь добавляет монеты и банкноты в сундуки без какой-либо системы и тут же дописывает нужные буквы в описи. Например, опись abbaHihihihI означает, что в сундуке лежат 7105 рублей и 12 копеек (две монеты номиналом 1 копейка; две монеты номиналом 5 копеек; три монеты номиналом 10 рублей; три монеты номиналом 25 рублей; одна банкнота номиналом 2000 рублей; одна банкнота номиналом 5000 рублей). Опись пустого сундука является пустой строкой.
Скупой рыцарь хочет найти в своём подвале два сундука, таких, чтобы после суммирования денежных сумм, лежащих в них, получился максимальный результат. Если в подвале есть несколько искомых пар сундуков, то скупой рыцарь выбирает из них такую пару, что сумма номеров сундуков максимальна.
Составьте программу, принимающую на вход в первой строке десятичное число N -- положительное натуральное число (2 ≤ N ≤ 1000) -- количество сундуков, а в последующих N строках -- описи сундуков с номерами от 1 до N. Известно, что в каждой описи не более чем 1000 букв, то есть, в каждом сундуке не более чем 1000 монет и/или банкнот. Программа находит номера K и L такие, что K<L, суммарное количество денег в K-ом и L-ом сундуках наибольшее и сумма K+L наибольшая. Программа выводит в первой строке найденное число K, а во второй строке -- L. Каждое число записывается в десятичной системе без знака.
Формат входных данных
В первой строке содержится десятичное число N — количество сундуков (2 ≤ N ≤ 1000). В следующих N строках содержатся описи сундуков -- последовательности, в которых могут встретиться только латинские буквы a, b, ..., i, A, B, ..., I. Длины строк находятся в диапазоне от 0 до 1000 включительно.
Формат результата
В первой строке выводится беззнаковое десятичное натуральное число K. Во второй строке выводится беззнаковое десятичное натуральное число L. Числа K и L таковы, что K<L, суммарное количество денег в K-ом и L-ом сундуках наибольшее и сумма K+L наибольшая.
Примеры
Входные данные
2
abbahihihi
CDFFGE
Результат работы
1
2
Входные данные
3
i
i
ai
Результат работы
2
3
Входные данные
4
h
bAA
eeeeeaeeeee
Bb
Результат работы
2
4*/