Cho ~n~ đồ vật, mỗi đồ vật có trọng lượng ~w_i~ , giá trị ~v_i~ và một chiếc túi có sức chứa tối đa ~W~.

Bạn có thể chọn mỗi đồ vật nhiều lần (không giới hạn số lượng). Hãy chọn các đồ vật sao cho tổng trọng lượng không vượt quá ~W~ và tổng giá trị là lớn nhất có thể.

Yêu cầu: Tìm giá trị lớn nhất có thể đạt được khi chọn một số (có thể lặp lại) các đồ vật, sao cho tổng trọng lượng không vượt quá sức chứa của túi ~W~.

Input

• Dòng thứ nhất: Hai số nguyên ~n,W~ - số lượng đồ vật và sức chứa túi (~1 \leq n,W \leq 1000~).
• ~n~ dòng tiếp theo chứa hai số ~w_i,v_i~ - trọng lượng và giá trị của vật thứ ~i~ (~1 \leq w_i \leq W, 1 \leq v_i \leq 10^9~).

Output

Một số nguyên duy nhất: giá trị lớn nhất có thể đạt được khi chọn đồ vật theo quy tắc trên.

Scoring

• Subtask ~1~ ~(70\%)~: ~1 \leq n \leq 20,1 \leq W \leq 1000~;
• Subtask ~2~ ~(30\%)~: Không rằng buộc giới hạn gì thêm.

  Example input 1

3 10
3 6
4 8
5 10

Example output 2

20

Note 1

• Chọn hai vật có trọng lượng 5, giá trị 10 → tổng = 10, giá trị = 20.
• Không có cách nào khác đạt giá trị cao hơn.