Freelancers game#7442
Serik and Zhomart are freelancers. They got orders from different companies. -th company gave them a_i tasks and agreed to pay b_i 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.
First line contains one integer (1 \le n \le 100) – number of companies. Each of the next lines contains two integers a_i (1 \le a_i \le 20) and b_i (1 \le b_i \le 10000) – the number of tasks and money given by -th company.
Output two integers – the money earned by Serik and Zhomart respectively.
Example 1
-st day Serik completes the only task given by fourth company and earns dollars
-nd day Zhomart completes the only task given by first company and earns dollars
-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 .