Có \(N\) món hàng được đánh số từ \(1\) đến \(N\). Món hàng thứ \(i\) sẽ có trọng lượng \(w_i\) và giá trị \(v_i\)

Hạo phải chọn một vài món hàng trong \(N\) món để mang về nhà. Nhưng Balo chỉ có thể chứa được tối đa \(W\).

Yêu cầu

• Hãy tính giá trị cao nhất mà Hạo có thể bỏ vào balo mang về.

Ràng buộc

• \(1 \le N \le 10^2\)
• \(1 \le W \le 10^5\)
• \(1 \le w_i \le W\)
• \(1 \le v_i \le 10^9\)

Dữ liệu vào

• Dòng đầu là hai số nguyên \(N\) và \(W\)
• \(N\) dòng tiếp theo, dòng \(i\) chứa 2 giá trị \(w_i v_i\)

Dữ liệu ra

• Giá trị cao nhất mà Hạo có thể mang về

Input 1

3 8
3 30
4 50
5 60

Output 1

90

Giải thích

Chọn món hàng 1 và 3, trọng lượng là 3+5=8, giá trị là 30+60=90