Đá quý và chiếc túi

Một chú bé được chim thần đưa tới đảo đá quý, trên đó có \(N\) viên đá. Viên thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Chú mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\); mỗi viên chỉ lấy tối đa một lần.

Hãy tìm tổng giá trị lớn nhất của các viên đá mà chú có thể mang về, sao cho tổng trọng lượng không vượt quá \(M\).

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 \(w_i\) và \(v_i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 100\)
• \(1 \le M \le 10^9\)
• \(0 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^3\)

Sample Input 1

4 10
6 40
5 30
4 35
7 20

Sample Output 1

75

Sample Input 2

2 1000000000
600000000 500
500000000 700

Sample Output 2

700

Explanation

Ví dụ 1: chọn viên 1 và viên 3 (nặng \(10\), giá trị \(75\)); các cặp khác nhẹ hơn nhưng giá trị nhỏ hơn. Ví dụ 2: hai viên có tổng cân nặng \(1.1 \cdot 10^9\) vượt quá \(M\), nên chỉ lấy được viên có giá trị \(700\).