|
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на
k
=
109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число
–
–
максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл
A
и файл
B
), каждый из которых содержит в первой строке количество троек
N
(1 ≤
N
≤ 1
000
000). Каждая из следующих
N
строк содержит три натуральных числа, не превышающих 12 000.
Пример организации исходных данных во входном файле:
6
1 3 7
5 12 6
6 9 11
5 4 8
3 5 4
1 1 1
Для указанных входных данных, в случае, если
k
=
5, значением искомой суммы является число 44.
В ответе укажите два числа: сначала значение искомой суммы для файла
А
, затем для файла
B
.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|