6852: 买一送一
[Creator : ]
Description
高桥去一个比萨店买比萨。店里有 $n$ 种比萨出售，第 $i$ 种的价格为 $p_i$ 元，美味度为 $d_i$。
比萨店正在开业酬宾，每购买 $1$ 个比萨，就可以免费获得一个售价更小的比萨。
于是高桥君重复以下购买比萨的过程：
选择一个比萨（假设是第 $i$ 种），花费 $p_i$ 元购买第 $i$ 种比萨。从价格小于 $p_i$ 元的比萨中选择一个，免费获得这个比萨。
高桥只有 $K$ 元，通过合理选择每次购买和免费获得的比萨，他最多可以得到的最大美味度的总和是多少？
比萨店正在开业酬宾，每购买 $1$ 个比萨，就可以免费获得一个售价更小的比萨。
于是高桥君重复以下购买比萨的过程：
选择一个比萨（假设是第 $i$ 种），花费 $p_i$ 元购买第 $i$ 种比萨。从价格小于 $p_i$ 元的比萨中选择一个，免费获得这个比萨。
高桥只有 $K$ 元，通过合理选择每次购买和免费获得的比萨，他最多可以得到的最大美味度的总和是多少？
Input
第一行包括两个整数 $n,k$。
第 $2 \sim n+1$ 行，每行两个整数 $p_i, d_i$。
第 $2 \sim n+1$ 行，每行两个整数 $p_i, d_i$。
Output
一行一个整数，表示答案。
Constraints
$1 \leq n \leq 300$
$1 \leq k \leq 10000$
$1 \leq p_i \leq k$
$1 \leq d_i \leq 5000$
$1 \leq k \leq 10000$
$1 \leq p_i \leq k$
$1 \leq d_i \leq 5000$
Sample 1 Input
4 20
6 2
10 50
10 50
20 50
Sample 1 Output
104
Sample 2 Input
6 101
100 1
100 10
100 100
101 1
101 2
101 3
Sample 2 Output
103
Sample 3 Input
8 887
181 89
133 464
29 2
379 434
86 351
8 103
902 489
1 124
Sample 3 Output
109988