有两个国家，帝国 Cacao 和公国 Cocoa。两位女孩，Alice（Cacao 女皇）和 Brianna（Cocoa 公主）是朋友，她们都非常喜欢巧克力。

有一天，Alice 发现了一个装满巧克力球的透明管子（图 I.1）。管子顶部只有一个开口。管子很窄，巧克力球排成一列。巧克力球用整数 $1, 2, \dots, N$ 编号，其中 $N$ 是巧克力球的总数。巧克力球 1 在最上方，靠近管口。巧克力球 2 紧挨着巧克力球 1，以此类推，巧克力球 $N$ 在管子的最底部。巧克力球只能从开口处取出，因此必须按照编号递增的顺序取出。

图 I.1. 装满巧克力球的透明管子

Alice 去拜访 Brianna，打算一起分享管子里的巧克力球。她们仔细观察了这些巧克力球，并估计了每个巧克力球 $i$ 的营养价值 $r_i$ 和美味程度 $s_i$。两位女孩都希望最大化自己吃到的巧克力球的美味程度之和。她们足够明智，能够和平地解决这一冲突，因此她们决定玩一个游戏，并按照以下规则吃掉巧克力球：

1. Alice 和 Brianna 的初始能量水平分别为非负整数 $A$ 和 $B$。
2. Alice 和 Brianna 轮流执行以下两种操作之一：
   • 跳过 (Pass)：不吃任何巧克力球。她会感到有点饿——具体来说，她的能量水平减少 1。当能量水平为 0 时，她不能选择跳过。
   • 吃 (Eat)：吃掉最上面的巧克力球——设该巧克力球为 $i$（即当前编号最小的巧克力球）。她的能量水平增加 $r_i$（营养价值），而不是减少 1。当然，巧克力球 $i$ 会从管子中移除。
3. Alice 先手。
4. 当所有巧克力球都被吃完时，游戏结束。

你是服务于 Alice 女皇的工作人员。你的任务是计算在双方都采取最优策略的情况下，Alice 和 Brianna 分别能获得的美味程度总和。

输入格式

输入包含单个测试用例。测试用例格式如下：

$N \ A \ B$ $r_1 \ s_1$ $r_2 \ s_2$ $\vdots$ $r_N \ s_N$

第一行包含三个整数 $N, A, B$。$N$ 表示巧克力球的数量，$A$ 和 $B$ 分别表示 Alice 和 Brianna 的初始能量水平。接下来的 $N$ 行描述了管子里的巧克力球。巧克力球编号从 1 到 $N$，每行包含两个整数 $r_i$ 和 $s_i$（$1 \le i \le N$），分别表示巧克力球 $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$

输出格式

输出两个整数，分别表示在双方采取最优策略的情况下，Alice 和 Brianna 能够获得的美味程度总和。

样例

样例输入 1

2 5 4
5 7
4 8

样例输出 1

8 7

样例输入 2

3 50 1
49 1
0 10
0 1

样例输出 2

10 2

样例输入 3

4 3 2
1 5
2 46
92 40
1 31

样例输出 3

77 45

样例输入 4

5 2 5
56 2
22 73
2 2
1 55
14 18

样例输出 4

57 93