Гра фрилансерів
Серік і Жомарт - фрілансери, які отримали замовлення від n різних компаній. i-та компанія доручила їм a[i] завдань і погодилася заплатити b[i] доларів після завершення всіх завдань. Оскільки у них лише один ноутбук, кожного дня працює лише один з них, виконуючи одне завдання на свій вибір. Вони домовилися, що будуть чергуватися щодня (Серік починає першим) у виконанні завдань, і той, хто завершить останнє завдання компанії, отримає всі гроші. Кожен з них прагне заробити якомога більше, тому обирає завдання оптимально. Визначте, скільки грошей заробить кожен з друзів.
Вхідні дані
Перша строка містить кількість компаній n (1 ≤ n ≤ 100). Кожен з наступних n рядків містить два цілі числа a[i] (1 ≤ a[i] ≤ 20) і b[i] (1 ≤ b[i] ≤ 10000) – кількість завдань і сума грошей, яку заплатить i-та компанія.
Вихідні дані
Виведіть два числа – кількість грошей, зароблених Серіком і Жомартом.
Зауваження
На 1-ий день Серік завершує перше завдання четвертої компанії і заробляє 8 доларів.
На 2-ий день Жомарт завершує єдине завдання першої компанії і заробляє 5 доларів.
На 3-ій день Серік завершує одне з трьох завдань третьої компанії, залишаючи ще дві задачі цієї компанії.
Залишаються по дві задачі у кожної компанії. Незалежно від дій Жомарта, Серік заробить решту грошей.
Загальний заробіток Серіка становить 8 + 4 + 6 = 18, а загальний заробіток Жомарта - 5.