Sweet War

Time limit1sMemory limit256 MB

Summary

Two players alternate passing at one energy each or eating the next ball for its nutrition and taste, and each maximizes total taste eaten.

Level: Hard8 of 10
Topics: Game theory, Dynamic programming
Solved: No attempts yet

Problem

There are two countries, Imperial Cacao and the Principality of Cocoa. Alice, the Empress of Cacao, and Brianna, the Princess of Cocoa, are friends, and both of them love chocolate.

One day Alice found a transparent tube filled with chocolate balls. The tube has a single opening at its top end, and it is so narrow that the chocolate balls sit in one line. The balls are numbered $1$ through $N$ . Ball $1$ is next to the opening, ball $2$ is right below it, and ball $N$ is at the bottom of the tube. A ball can leave the tube only through the opening, so the balls must be taken out in increasing order of their numbers.

Alice visited Brianna to share the tube. They looked at the balls carefully and decided that ball $i$ has nutrition value $r_i$ and deliciousness $s_i$ . Each of them wants to maximize the total deliciousness of the balls she eats. To settle this peacefully, they play a game with the following rules.

Alice starts with energy $A$ and Brianna starts with energy $B$ . Both are nonnegative integers.
The two players take turns, and on her turn a player takes one of the two actions below.
- Pass: she eats nothing. She gets a little hungry, so her energy level drops by $1$ . She cannot pass when her energy level is $0$ .
- Eat: she eats the topmost chocolate ball. If that ball is ball $i$ , she gains deliciousness $s_i$ and her energy level rises by $r_i$ . Her energy level does not drop by $1$ in this case. Ball $i$ is removed from the tube.
Alice takes the first turn.
The game ends when every chocolate ball has been eaten.

Compute the total deliciousness Alice gets and the total deliciousness Brianna gets when both play optimally.

Input

The input is a single test case in the following format.

N A B
r1 s1
r2 s2
...
rN sN

The first line has three integers $N$ , $A$ , and $B$ . $N$ is the number of chocolate balls, and $A$ and $B$ are the initial energy levels of Alice and Brianna. Each of the next $N$ lines describes one ball, from the top of the tube down. The $i$ -th of those lines has the nutrition value $r_i$ and the deliciousness $s_i$ of ball $i$ .

$1 \le N \le 150$
$0 \le A, B, r_i \le 10^9$
$0 \le s_i$
$\sum_{i=1}^{N} s_i \le 150$

Output

Print two integers on one line, separated by a space: the total deliciousness Alice gets and the total deliciousness Brianna gets when both play optimally.

Examples4

Example 1
Input
```
2 5 4
5 7
4 8
```
Expected output
```
8 7
```
Example 2
Input
```
3 50 1
49 1
0 10
0 1
```
Expected output
```
10 2
```
Example 3
Input
```
4 3 2
1 5
2 46
92 40
1 31
```
Expected output
```
77 45
```
Example 4
Input
```
5 2 5
56 2
22 73
2 2
1 55
14 18
```
Expected output
```
57 93
```