文件读写

• 输入文件 supply.in
• 输出文件 supply.out

限制

• 1000ms
• 512MB

题目描述

程老师带科考队进山考察，山脚下的补给站里备着 $n$ 件装备。第 $i$ 件装备的重量是 $w_i$ 公斤，重要度是 $v_i$。装备有轻有重，轻的像绳子、望远镜，重的像帐篷、锅具；重要度是程老师事先给每件装备打的分数，分数越高，这一路上越用得上。科考队要在山里待上许多天，行李全靠人背，能少带就少带，可有些装备又非带不可，怎么取舍，程老师想了一路。补给站里每一件装备都只有一件，谁拿走了，货架上就空了，不会有第二件补上来。

进山要好几天，吃住都在野外，程老师叫上常年走山路的向导一起，两人各背一个背包。程老师的背包容量是 $W_1$ 公斤，向导的背包容量是 $W_2$ 公斤。一个背包能装下的装备，总重量不能超过它自己的容量：把装进这个背包的每一件装备的重量加起来，这个总重量不超过背包容量，就算装得下；超过了，背包就背不动了。两个背包的容量各有限制，不能互相借，谁背得动多少就是多少。

收拾装备的时候，每一件装备都摆在面前，程老师挨个决定它的去处：可以放进自己的背包，可以放进向导的背包，也可以留在补给站不带。程老师手里有一张清单，把每件装备的重量和重要度都记在上面，收拾的时候照清单一件一件过，每件装备的去处定了，就在清单上划掉一笔。一件装备是一个整体，要么整个放进某个背包，要么整个不带，不能拆开。两个背包各装各的，互不帮忙：程老师的包能装多少，向导的包帮不上忙；向导的包能装多少，也占不了程老师包里的地方。一件装备装进了程老师的包，就不能再放进向导的包，同一件装备不能同时出现在两个背包里。

程老师想知道，在程老师的背包和向导的背包都不超重的前提下，两个人带走的所有装备的重要度总和最大是多少。

输入格式

第一行三个整数 $n, W_1, W_2$，分别表示装备件数、程老师背包容量和向导背包容量。

接下来 $n$ 行，每行两个整数 $w_i, v_i$，分别表示第 $i$ 件装备的重量和重要度。

输出格式

一行一个整数，表示两人带走的所有装备的重要度总和的最大值。

数据范围

特殊性质 A：$W_2 = 0$。

特殊性质 B：所有装备的重量均为 $1$ 公斤。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$0 \leq W_1, W_2 \leq 200$，$1 \leq w_i \leq 50$，$1 \leq v_i \leq 10^6$。

3 5 5
3 10
3 9
3 8

19

3 4 4
3 11
3 9
2 8

20

样例解释

样例 1：三件装备的重量都是 3 公斤，任意一个背包都只能装下其中的一件，所以能带走的装备至多两件。取重要度最大的两件 10 和 9，分别放进程老师的背包和向导的背包，总重要度 19。