分数: 6 点
问题陈述
高桥有 N 零食。 对于 i = 1, 2, \ldots, N, i第零食的重量为 w_i 和美味 v_i.
高桥将选择任何数字(可能 0)的 N 明天学校旅行要带的零食。 高桥有两个背包。 他在学校旅行中带的每一份零食都应该装进两个背包中的一个。 这里,第一个背包中零食的重量之和最多应为 A, 第二个背包中零食的重量之和最多为 B.
找出他在学校旅行中可以携带的零食的最大可能总口味。
约束
- 1 \leq N \leq 100
- 1 \leq A, B \leq 300
- 1 \leq w_i \leq 300
- 1 \leq v_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A B w_1 v_1 w_2 v_2 \vdots w_N v_N
输出
打印答案。
示例输入 1
6 8 9 2 6 4 1 5 9 3 1 5 3 5 8
示例输出 1
24
他可以把 1-st 和 3-第一个背包里的零食,
和 2-nd 和 6第二个背包里的第个零食。
那么,第一个背包中零食的重量总和为 w_1 + w_3 = 2 + 5 = 7,
第二个背包里的零食总和是 w_2 + w_6 = 4 + 5 = 9,不超过各自背包的上限, A = 8, B = 9.
他修学旅行带的零食的总味道是 v_1 + v_2 + v_3 + v_6 = 6 + 1 + 9 + 8 = 24,这是最大值。
示例输入 2
20 70 60 7 94 18 33 14 26 10 1 9 57 2 80 19 74 16 10 15 18 10 38 13 90 12 23 3 3 8 11 18 10 3 42 3 66 3 90 10 2 5 45
示例输出 2
772