gramezi

Захарел и Бронзарел играят следната игра: N купчинки от монети са поставени на масата. Дадено е, че ако Захарел избере i-тата купчинка, той ще вземе Ai монети от нея, а ако Бронзарел избере същата купчинка, ще вземе Bi  монети от купчинката. Известно е, че всяка купчинка има поне max(Ai,Bi) монети. След като играчът е взел монети от някоя купчинка, останалите монети от купчинката се изхвърлят. Двамата играчи се редуват да избират купчинки и вземат монети, докато ги изчерпят. Захарел започва пръв. На края на играта печели този, който е събрал повече монети. Ако двамата са събрали по равен брой монети, играта завършва наравно.

Задача

При условие, че Захарел и Бронзарел играят оптимално, определете броя на монетите, които всеки от играчите ще събере на края на играта. Под оптимална игра разбираме, че всеки играч се стреми да увеличи разликата между броя на монетите, които той ще събере накрая и броя, който ще събере противникът и ако има няколко възможности за това, всеки се стреми да събере повече монети.

Вход

Първият ред на входния файл gramezi.in съдържа цялото положително число N. Следващите N реда съдържат по две цели положителни числа, разделени с интервал. Тези числа задават съответните стойности на Ai и Bi.

Изход

Първият ред на изходния файл gramezi.out трябва да съдържа две цели положителни числа, разделени с интервал. Тези числа трябва да показват резултатите на Захарел и Бронзарел.

Ограничения

1 <= N <= 30 000
1 <=
Ai, Bi <= 30 000

Пример

gramezi.in

gramezi.out

Обяснение

4
2 10
5 5
7 3
4 1

9 6

Има 4 купчинки с монети.
Ако Захарел вземе купчинка 1, ще получи 2 монети, но ако Бронзарел вземе купчинка 1, той ще получи 10 монети.
Ако Захарел вземе купчинка 2, ще получи 5 монети, ако Бронзарел вземе купчинка 2, той ще получи 5 монети.
Ако Захарел вземе купчинка 3, ще получи 5 монети, ако Бронзарел вземе купчинка 3, той ще получи 3 монети.
Ако Захарел вземе купчинка 4, ще получи 4 монети, ако Бронзарел вземе купчинка 4, той ще получи 1 монета.

Решението е: Захарел взема купчинка 1 (Захарел получава 2 монети), тогава Бронзарел взема купчинка 2 (Бронзарел взема 5 монети). След това Захарел взема купчинка 3 (Захарел получава 7 монети). Накрая Бронзарел взема купчинка 4 (Бронзарел получава 1 монета).
Друго развитие на играта със същата разлика в монетите е: Захарел взема купчинка 1, после Бронзарел взема купчинка 3, след това Захарел взема купчинка 2 и накрая Бронзарел взема купчинка 4. Това води до резултат 7 на 4, но тези числа са по-малки отколкото при първия вариант, когато резултатът е 9 на 6.

 Време за работа на програмата: 0.1 секунди за тест.

Mircea Paşoi
University of Bucharest, Mathematics & IT Department
bogdanpasoi@yahoo.com

Превод на български: Емил Келеведжиев