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