题目描述

高桥在一家自助餐馆里。

这家餐馆提供 $N$ 种菜品。吃第$i$种菜需要 $A_i$ 分钟，其美味程度为 $B_i$;。

这个餐馆有以下规则: ”你一次只能点一道菜。点的菜会立即送过来，可以马上吃。

”不能重复点同一种菜。

在你吃完已经送到的菜之前，不能点新的菜。

从第一道菜下单开始算起的 $T - 0.5$ 分钟后，不能再点新的菜，但你可以继续吃已经上菜的菜.。

高桥的幸福感定义为他在这家餐馆里吃到的菜的美味程度总和。

在做出最优选择的情况下，高桥能达到的最大幸福感是多少?

输入

输入第一行两个整数$N,T$

接下来一共$N$对数$A_i,B_i$

输出

输出高桥能达到的最大幸福感。

2 60
10 10
100 100

110

样例解释

按照这个顺序点第一道菜和第二道菜，高桥的幸福感将达到 110。

需要注意的是，如果我们能够在时间内下单，就可以花费任意多的时间来吃它。

3 60
10 10
10 20
10 30

60

样例解释

高桥可以在 60 分钟内吃完所有菜。

3 60
30 10
30 20
30 30

50

样例解释

按照这个顺序点第二道菜和第三道菜，高桥的幸福感将达到 50。

无论以哪种顺序点菜，我们都无法点三道菜。

10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

145

提示

• $2\ \leq\ N\ \leq\ 3000$
• $1\ \leq\ T\ \leq\ 3000$
• $1\ \leq\ A_i\ \leq\ 3000$
• $1\ \leq\ B_i\ \leq\ 3000$