gramezi

Zaharel and Bronzarel play the following game: N piles of coins are placed on the table. We know that if Zaharel takes pile i he receives Ai of the coins in the pile, and if Bronzarel takes pile i he receives Bi of the coins in the pile (we know that each pile has at least max(Ai, Bi) coins and the remaining coins are thrown away). The two players alternate in taking a pile, until all N are used up, and Zaharel is the first to take a pile. In the end, the player with the most coins wins. If the number of coins is equal, the game is considered a draw.

Task

Knowing that Zaharel and Bronzarel play optimally, determine the number of coins each player will have at the end. By optimum game we understand that each player will attempt to increase the difference between the number of coins he has and the number of coins the other player has, and if he has more than one possibility to obtain this difference he will try to increase his number of coins.

Input Data

Line one of input file gramezi.in contains positive integer N. The following N lines will contain two positive integers separated by a space, representing values Ai and respectively Bi.

Output Data

Line one of file gramezi.out will contain two positive integers separated by space representing Zaharel's and respectively Bronzarel's score.

Restrictions

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

Examples

gramezi.in

gramezi.out

Explanation

4
2 10
5 5
7 3
4 1

9 6

There are 4 piles of coins.
If Zaharel takes pile 1 he receives 2 coins, but if Bronzarel takes pile 1 he receives 10 coins.
If Zaharel takes pile 2 he receives 5 coins, and also if Bronzarel takes pile 2 he receives 5 coins.
If Zaharel takes pile 3 he receives 7 coins, but if Bronzarel takes pile 3 he receives 3 coins.
If Zaharel takes pile 4 he receives 4 coins, but if Bronzarel takes pile 4 he receives 1 coin.

The solution is: Zaharel takes pile 1 (Zaharel gets 2 coins), then Bronzarel takes pile 2 (Bronzarel gets 5 coins) then Zaharel takes pile 3 (Zaharel gets 7 coins), then Bronzarel takes pile 4 (Bronzarel gets 1 coin).
Another game play possibility with the same score difference is: Zaharel takes pile 1, then Bronzarel takes pile 3, then Zaharel takes pile 2, then Bronzarel takes pile 4. This would result in scores 7, and respectively 4, but these numbers of coins are smaller than the first option.

 Time limit: 0.1 seconds/test

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