Question

на c++ с циклом for

В новом игровом телешоу «Выбирай или проиграешь!» игроку по очереди даются пары призов ценностью ai и bi. Игрок может выбрать из каждой пары призов ровно один (разумеется, как правило, игроки выбирают более ценный приз).


Однако сложность игры в том, что в самом конце, когда пары призов закачиваются, игрок теряет все выигранное, если сумма ценностей его призов будет нечётной. Ровно поэтому грамотные игроки стараются поддерживать сумму призов чётной.


Программист Вася взломал сервер телешоу, и теперь облагает редкой (и ценной) информацией о том, какие пары призов будут в ближайшем телешоу.


Помогите ему определить, какую максимальную сумму ценностей призов он может получить.


Формат входных данных

В первой строке с клавиатуры вводится одно целое число n (1≤n≤105) — количество пар призов.

В следующих n строках вводятся целые числа ai и bi (0≤ai,bi≤104) — стоимости пары призов.


Формат выходных данных

Выведите на экран одно число — максимальную сумму, которую может получить игрок в «Выбирай или проиграешь!», если он обладает полной информацией о заготовленных парах призов.

Примечания

В первом примере из условия игрок всегда лишается всего своего выигрыша, потому что независимо от его выбора сумма будет нечётной, поэтому ответ равен 0.


Во втором примере после выбора в первой паре призов, игрок получает нечётную сумму, поэтому во второй паре он тоже должен выбрать приз нечётной ценности.


В третьем примере игрок может брать максимальные призы в каждой паре и сумма будет чётной.


Примеры

Answer 1

Код находится в приложении.