Курс: Подготовка к ЕГЭ

Модуль: B27 (C4) - анализ пар

Задачи

Задача

2/23

73. Выборка чисел из тройки для максимальной суммы, не кратной 4

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Задача

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 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