题目描述
远足携带大小两个背包,容量分别为 , 。共 件物品,第 件重 、价值 ,每件放进其中一个背包或放弃。两个背包各自都不超容的前提下,求带走的最大总价值。
输入格式
第一行三个整数 , , ;接下来 行每行 , 。
输出格式
一行一个整数,最大总价值。
样例
输入
4 5 5 3 7 4 9 2 5 3 6
输出
21
数据范围
- 对于 30% 的数据, 15 且 , 30(每件三去向暴力可过)。
- 对于 60% 的数据, 50 且 , 100。
- 对于 100% 的数据,1 100,1 , 200,1 , 200。