You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

苹之助是个贪心的孩子。来到一个到处都是草药的山洞里，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。苹之助有一段时间，在这段时间里，可以采到一些草药，请让苹之助采到的草药的总价值最大。

输入格式

第一行有 $2$ 个整数$M$（$1 \le M \le 1000$）和 $T$（$1 \le T \le 1000$），用一个空格隔开，$M$ 代表山洞里的草药的数目， $T$ 代表总共能够用来采药的时间。

接下来的 $M$ 行每行包括两个在 $1$ 到 $1000$ 之间（包括 $1$ 和 $1000$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

3 70
71 100
69 1
1 2

3