Bạn có n món đồ, mỗi món có:

Giá trị value[i]

Trọng lượng weight[i]

Bạn có một cái balo có sức chứa tối đa là W.

Hãy chọn một tập hợp các món đồ sao cho:

Tổng trọng lượng không vượt quá W

Tổng giá trị là lớn nhất có thể

Dữ liệu vào (Input)

Dòng đầu chứa hai số nguyên n và W (1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴).

Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên weight[i] và value[i] (1 ≤ weight[i], value[i] ≤ 10⁴).

Dữ liệu ra (Output)

In ra giá trị lớn nhất có thể đạt được.

Ví dụ:

Input

4 7
6 13
4 8
3 6
5 12

Output

14

Giải thích: Chọn món 2 và món 3 → tổng trọng lượng = 4 + 3 = 7 ≤ 7,

tổng giá trị = 8 + 6 = 14.