自助餐 - 代码源竞赛平台

题目描述

蜗蜗来到一家自助餐馆。这里有 $N$ 种料理，第 $i$ 种料理需要 $A_i$ 分钟吃完，美味度为 $B_i$ 。

每次只能点一道料理，点后立即上菜。吃完当前料理才能点下一道，且同一种料理最多点一次。从第一次点餐开始，经过 $T-0.5$ 分钟后，餐馆不再接受新订单；已经点好的料理仍可以继续吃完。

蜗蜗可以自行决定点餐顺序和要点的料理。求他能吃到的料理的最大美味度总和。

第一行包含两个整数 $N,T$ ，分别表示料理种数和停止点餐的时间参数。

接下来 $N$ 行，每行包含两个整数 $A_i,B_i$ ，表示一种料理的用餐时间和美味度。

输出一行一个整数，表示能够获得的最大美味度总和。

2 2
2 10
1 7

样例 1 中，先吃耗时 $1$ 分钟、美味度为 $7$ 的料理，再在第 $1$ 分钟点耗时 $2$ 分钟、美味度为 $10$ 的料理，总美味度为 $17$ 。最后一道料理可以在停止点餐后继续吃。

样例 2 中，先吃第三道料理，再点第二道料理，可得到 $5+9=14$ 的美味度。

对于 100% 的数据，保证 $2\le N\le 3000$ ， $1\le T\le 3000$ ， $1\le A_i,B_i\le 3000$ 。