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 of input 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.