Serik and Zhomart are freelancers. They got orders from n different companies. i-th company gave them ai tasks and agreed to pay bi dollars when they finish all of the tasks they give. Serik and Zhomart have only one laptop, so each day only one of them works and completes only one task which is selected by his own choice. Furthermore, they agreed that each day they alternate (Serik starts first) in performing tasks and who completes the last task of a company will get all the money given by that company. Each of them wants to earn much. Thus, they select tasks optimally. Find the money earned by each of them.

Input

First line contains one integer n (1 ≤ n ≤ 100) – number of companies. Each of the next n lines contains two integers ai (1 ≤ ai ≤ 20) and bi (1 ≤ bi ≤ 10000) – the number of tasks and money given by i-th company.

Output

Output two integers – the money earned by Serik and Zhomart respectively.

Note

1-st day Serik completes the only task given by fourth company and earns 8 dollars

2-nd day Zhomart completes the only task given by first company and earns 5 dollars

3-rd day Serik completes one of the three tasks given by third company and there remains two tasks of this company

There remained two tasks of each company. No matter how Zhomart will act, Serik earns all the remaining money.

So, total earnings of Serik 8 + 4 + 6 = 18 and total earnings of Zhomart 5.