Выборка чисел из тройки для максимальной суммы, не кратной 4
Задача
Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите эффективную программу, решающую поставленную задачу.
Входные данные:
На вход программе в первой строке подаётся количество троек N (1 <= N <= 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
| Ввод |
Вывод |
|
6
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
|
63 |