Kim cương vô hạn

Trên một hòn đảo có \(N\) loại kim cương, mỗi loại có vô số viên. Một viên kim cương loại \(i\) có giá trị \(a_i\) và thể tích \(b_i\). Chiếc túi của bạn có sức chứa (tổng thể tích) là \(M\).

Hãy chọn các viên kim cương (mỗi loại có thể lấy nhiều viên, hoặc không lấy) sao cho tổng thể tích không vượt quá \(M\) và tổng giá trị là lớn nhất. In ra tổng giá trị lớn nhất đó.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).

Output

In ra một số nguyên: tổng giá trị lớn nhất có thể đạt được.

Constraints

• \(1 \le N \le 1000\)
• \(1 \le M \le 11111\)
• \(0 \le a_i \le 10^9\)
• \(1 \le b_i \le 10^4\)

Sample Input

3 10
7 3
5 2
11 4

Sample Output

27

Explanation

Lấy hai viên loại 3 (thể tích \(8\), giá trị \(22\)) và một viên loại 2 (thể tích \(2\), giá trị \(5\)): tổng thể tích \(10\), tổng giá trị \(27\). Không có cách nào tốt hơn.