Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на
4
и при этом была максимально возможной.
Формат входных данных
В первой строке количество пар
N
(1 ≤
N
≤ 100000). Каждая из следующих
N
строк содержит два натуральных числа, не превышающих 10 000.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Формат выходных данных
Выведите значение найденной максимальной суммы. Если такой суммы нет, то выведите
-1
.
Примеры
№ | Входные данные | Выходные данные |
1
|
3
5 8
13 5
26 4
|
44
|