Cho \(N\) món hàng. Món hàng \(i\) có giá trị \(v_i\) và trọng lượng \(w_i\). Bạn hãy tìm cách đặt các món hàng vào ba lô sao cho:

• Tổng giá trị các món hàng là lớn nhất
• Tổng trọng lượng phải nhỏ hơn \(W\) (là trọng tải ba lô có thể mang được).

Input

• Dòng thứ nhất chứa hai số \(N\) và \(W\). \(N\) là số lượng loại hàng, \(W\) là trọng tải của balô.
• Các dòng tiếp theo, là các cặp giá trị \(v_i\) và \(w_i\)

Output

• Một số nguyên duy nhất là tổng giá trị món hàng có thể bỏ vào ba lô.

• \(1 \le N \le 100\)
• \(1 \le v_i \le 1000\)
• \(1 \le w_i \le 1000\)
• \(1 \le W \le 10000\)

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9