题目描述

现在 zql 手上有 N 道题，他总共有 T 的时间来完成他们中的一些或全部。每道题有一个完成所需时间 $t_i$ 和一个难度系数 $c_i$ 。如果 zql 在剩余 x 个单位时间的时候开始做题 i，并且能够完成，那么总分加上 x*c[i]。现在 zql 要从这 N 道题中选出一些在 T 个单位时间内完成，并且按照某种顺序依次完成它们（zql 每个单位时间只能做一道题，并且一旦他决定做某题就会一直做直到做完），那么他最多能够拿到多少分呢？

输入格式

第一行，两个用空格隔开的正整数 N 和 T，分别表示题目总数和总时间。

第 2 到 N+1 行，每行包含两个正整数，第 i+1 行的两个正整数分别表示 $t_i$ 和 $c_i$ 。

数据范围

对于 20% 的数据，N ≤ 8，T ≤ 200 。

对于 60% 的数据，N ≤ 15，T ≤ 1000 。

对于 90% 的数据，N ≤ 2000且满足 T 不小于做完 N 道题所需时间的总和。

对于 100% 的数据，N ≤ 3000，T≤10000，所有 $t_i$ 和 $c_i$ 均不超过 100 。保证答案在 32 位有符号整型范围内。

输出格式

一个整数，表示最大能够得到的分数。

样例

3 10
2 1
8 9
2 5

122

3 12
3 6
7 5
4 2

117

样例解释

样例 1 ：最优方案为在剩余 10 个单位时间的时候开始做第 3 题（需要 2 个单位时间），剩余 8 个单位时间的时候开始做第 2 题（需要 8 个单位时间），总得 分为 10×5+(10-2)×9=122。