Cho ~ n ~ loại đồ vật, loại đồ vật thứ ~ i ~ có khối lượng ~ a_i ~ và giá trị ~ b_i ~. Hãy chọn các đồ vật bỏ vào ba lô sao cho khối lượng của các đồ vật được chọn không vượt quá ~ W ~ và giá trị các đồ vật được chọn là lớn nhất. Mỗi đồ vật có số lượng không hạn chế.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số nguyên dương ~ n ~ và ~ W ~. ~ ( 1 ≤ n ≤ 1000, 1 ≤ W ≤ 10000) ~
• ~ n ~ dòng tiếp theo mỗi dòng ghi 2 số nguyên dương mô tả một đồ vật có trọng lượng ~ x ~ và giá trị ~ y ~ ~ ( 1 ≤ x, y ≤ 10000) ~

Kết quả

Một số nguyên dương là tổng giá trị lớn nhất đạt được.

Ràng buộc

Ví dụ:

Input 1

```9 84 7 1 4 2 1 1 2 6 2 3 3 7 8 6 4 4 6 9

```

Output 1

252