Cho ~n~ đồ vật, mỗi vật có trọng lượng ~w_i~ và giá trị ~v_i~. Cho một cái có sức chứa ~W~. Chọn một số đồ vật cho vào túi sao cho tổng trọng lượng không vượt quá ~W~ và tổng giá trị là lớn nhất. Mỗi vật chỉ có thể chọn một lần.

Yêu cầu: In ra tổng giá trị lớn nhất có thể đạt được khi cho các đồ vật vào túi.

Input

• Dòng đầu tiên: hai số nguyên ~n~ và ~W~ - số lượng đồ vật và sức chứa của túi (~1 \leq n,W \leq 1000~).
• ~n~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~w_i~ và ~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

In ra tổng giá trị lớn nhất có thể đạt được khi cho các đồ vật vào túi.

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

4 8
2 3
3 4
4 5
5 6

Example output 2

10

Note 1

• Chọn các đồ vật có trọng lượng 3 và 5 → tổng trọng lượng 8, tổng giá trị 10 (lớn nhất).