Có \(n\) món đồ, món đồ thứ \(i\) có cân nặng \(w_i\) và giá trị \(v_i\). Bạn có thể chọn số lượng món đồ túy ý miễn cân nặng không quá \(S\). Hãy tìm cách chọn đồ để có được giá trị lớn nhất.

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n\), \(S\).
• Mỗi dòng trong \(n\) dòng tiếp theo gồm \(2\) số nguyên \(w_i\), \(v_i\).

Output

• Một số nguyên duy nhất giá trị lớn nhất có thể đạt được. ### Điều kiện
• \(1 \le n \le 10^{2}\)
• \(1 \le S \le 10^{5}\)
• \(1 \le w_i, v_i \le 10^{5}\)

Sample Input 1

3 5
1 4
4 1
2 100

Sample Output 1

104