Denis has N boxes (N even), and each box contains M marbles which are either black or white. He knows for each box how many black marbles it contains and how many white marbles it contains. He now wants to split the N boxes into 2 groups, each containing N/2 boxes, such that the sum of the black marbles in the first group, and the white marbles in the second group is maximum.
Input
The first line of input contains N and M, in this order.
The following N lines contain two positive integers each, denoting the number of white marbles and the number of black marbles that are in each box.
Output
On a single line print two integers separated by space: the number of black marbles in the first group and the number of white marbles in the second group.
Constraints
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ 104
- The solution is unique.
Sample
| Input | Output |
|---|---|
| 4 3 0 3 3 0 1 2 2 1 | 5 5 |
