‹ 上一题 下一题 ›

g6-08012. 太空补给·二维费用 未做

1000 ms 256 MB 测试点 ? 6级·0/1背包GESP-6加维与变形

题目描述

小杨要去太空旅行:货舱里有 件补给,第 件占体积 、重 、价值 ,每件只有一件,最多带一次;货舱容积上限为 、承重上限为 。求他能带走的最大总价值。

输入格式

第一行三个整数 。

接下来 行,每行三个整数 。

输出格式

一行一个整数,表示最大总价值。

样例

输入 1

3 5 5
3 3 4
2 2 3
2 2 3

输出 1

7

选第 2、3 件:体积 4、承重 4、价值 7。

数据范围

,,。

输入
输出

            
答案