Дана последовательность, которая состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел имела такую же последнюю цифру, как наибольшая возможная, и при этом была минимальной возможной.
Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимальную возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл А и файл В, каждый из которых содержит в первой строке количество чисел N (1 <_ N <_ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.
Пример входного файла:
6
2 7
1 8
10 2
6 4
3 3
3 10
Для указанных данных максимальная сумма — 44 (7 + 8 + 10 + 6 + 3 + 10), её последняя цифра 4. Искомая минимальная сумма, имеющая последнюю цифру 4, равна 24, она соответствует выбору чисел (2 + 8 + 2 + 6 + 3 + 3).
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла В.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
(полученное из первого файла)
(полученное из второго файла)
«Некрыловские варианты» от Евгения Джобса — Вариант 5