~N~ карток викладені в ряд зліва направо. На кожній картці написано два натуральні числа, одне вгорі й цианового (ось такого) кольору, інше внизу й фіолетового (ось такого) кольору. Два гравці по черзі забирають по одній картці, причому забирати можна або крайню ліву, або крайню праву. Закінчується гра, коли забрано всі картки, пропускати хід не можна. Мета гри – отримати якомога більшу суму, враховуючи, що 1-й гравець враховує й додає лише верхні цианові числа своїх карток, 2-й гравець враховує й додає лише нижні фіолетові числа своїх карток.

Якими будуть результати гри при правильній грі обох гравців?

Вхідні дані

У першому рядку вказано кількість карток ~N~ (~1 \leqslant N \leqslant 30~). Далі йдуть ~N~ рядків, кожен з яких містить записані через пропуск (пробіл) рівно два натуральні числа, записані на відповідній картці, спочатку верхнє цинанове, потім нижнє фіолетове. Гарантовано, що всі ~2N~ чисел різні, всі є цілими степенями двійки і перебувають у межах від ~2^0~ до ~2^{60}~, обидві межі включно.

Результати

Виведіть в одному рядку через пропуск два цілі числа – результати гри при правильній грі обох гравців: спочатку суму цианових чисел, яку набере 1-й гравець, потім суму фіолетових чисел, яку набере 2-й гравець.

Приклади

Вхід

4
1024 8
256 512
4 2
16 65536

Результат

1280 65538

Вхід

4
1 2
8 64
1024 256
32 16

Результат

1025 80

Вхід

4
1 2
8 256
1024 64
32 16

Результат

1056 258

Примітка

Вказані величини досягаються такими, наприклад, способами:

Для прикладів 1 та 2 (але не 3) півходи 2-го гравця (2-й і 4-й) можна переставити місцями, й вийде інший спосіб набрати ті самі суми.