NOIP--分组背包问题

题目描述:

有个蒟蒻在NOIP（全国青少年信息学奥林匹克联赛）初赛中晋级了，他现在要参加NOIP复赛。

本次复赛有N道题目，每道题目满分100(?)分，总时间M分钟。

他看到题面后，他知道了完成每道题目的部分分和100(?)分的时间。

我们称每个部分分为一个分数档。

求他最多能得到的分数。

输入格式:

第1行2个数N，M。

接下来N行第1个数为每个题目的分数档个数Xi，然后每2个数一对，第1个数为完成该分数档需要的时间，第2个数为该分数档的分数。

输出格式:

输出最多能得到的分数

样例输入:

4 210
1 6 100
2 6 50 21 100
3 6 20 24 50 57 100
4 22 10 56 30 91 60 145 100

样例输出:

360

提示:

分组背包问题

N<=100，M<=10000，Xi<=100

所有分数档分数不超过20000

时间限制: 1000ms
空间限制: 256MB

---

来源: by qq1010903229