← 返回题目列表

AtCoder · past202206_h

H. 两个背包

中文机器翻译题面 查看原题

分数: 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