‹ 上一题 下一题 ›

g6-07943. 容量为 0 未做

1000 ms 256 MB 测试点 ? 6级·0/1背包GESP-601模型与状态状态与转移

题目描述

小杨的背包容量 。他面前有 件物品,第 件重 、价值 ,而所有物品的重量都至少为 ,所以哪一件都装不下。请输出他能带走的最大总价值。注意 可能很大,请使用较快的读入方式。

输入格式

第一行两个整数 (保证 )。

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

输出格式

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

样例

输入 1

3 0
5 10
2 7
9 3

输出 1

0

数据范围

,,。

输入
输出

            
答案