Nhặt vàng cho vào túi

Một người thợ kim hoàn tới hầm mỏ có \(N\) viên quặng vàng. Viên quặng thứ \(i\) có giá trị \(a_i\) và chiếm thể tích \(b_i\). Chiếc balô của anh có sức chứa tổng cộng là \(M\) (đơn vị thể tích). Mỗi viên quặng chỉ được mang đi tối đa một lần.

Hãy chọn một số viên quặng sao cho tổng thể tích không vượt quá \(M\) và tổng giá trị là lớn nhất có thể. 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\): giá trị và thể tích của viên quặng thứ \(i\).

Output

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

Constraints

• \(1 \le N \le 1000\)
• \(1 \le M \le 1000\)
• \(0 \le a_i \le 10^5\)
• \(0 \le b_i \le 10^5\)

Sample Input

4 9
10 4
7 5
12 6
3 2

Sample Output

17

Explanation

Chọn viên 1 (thể tích 4) và viên 2 (thể tích 5): tổng thể tích \(9\), tổng giá trị \(17\). Chọn viên 3 và viên 4 (thể tích \(8\)) cho giá trị \(15\); chọn viên 1, 4 (thể tích \(6\)) chỉ được \(13\). Đáp án là \(17\).