a27_0007

Дана информация о числовых кодах парных деталей, которые планируется использовать при сборке изделий. Информация о каждой паре деталей представлена в виде пар положительных целых чисел. Из каждой пары деталей, руководствуясь их кодами, необходимо выбрать одну деталь таким образом, чтобы сумма кодов всех выбранных деталей не делилась на 13 и при этом была максимально возможной.

Определите максимально возможную сумму кодов деталей, соответствующую условию задачи.

Входные данные

Дано два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N (1 ≤ N≤ 10 000 000) - количество пар деталей. В каждой из следующих N строк находится два числа: коды деталей (все числа натуральные, значения кода каждой детали не превышает 1000).

В ответе укажите два числа: сначала значение искомой величины для файла А, затем - для файла В.

Типовой пример организации данных во входном файле

6

1 3

5 12

6 9

5 4

5 5

1 1

При таких исходных данных и критерии отбора кодов, согласно которому сумма не должна делиться на 7, искомая сумма кодов равна 34.

**Типовой пример имеет иллюстративный характер.Для выполнения задания используйте данные из прилагаемых файлов.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Файлы к заданию:

• a27_0007A.txt
• a27_0007B.txt