Một tên trộm đột nhập vào một cửa hàng. Hắn mang theo một cái túi có sức chứa tối đa là $W$. Trong cửa hàng có $N$ món đồ, món đồ thứ $i$ có trọng lượng là $\text{weight}[i]$ và giá trị là $\text{value}[i]$.
Tên trộm muốn lấy đi những món đồ sao cho tổng giá trị của chúng là lớn nhất có thể, nhưng tổng trọng lượng không được vượt quá sức chứa $W$ của cái túi. Với mỗi món đồ, hắn chỉ có hai lựa chọn: lấy hoặc không lấy (không thể lấy một phần của món đồ).

Input (Dữ liệu vào)

• Dòng 1: Chứa hai số nguyên $N$ (số món đồ) và $W$ (sức chứa tối đa của túi).
• Dòng 2: Chứa $N$ cặp số nguyên (trọng lượng và giá trị) cách nhau một dấu cách.

Output (Kết quả)

• Tổng giá trị lớn nhất của các món đồ có thể lấy mà không vượt quá trọng lượng $W$.

Subtasks (Ràng buộc)

• Subtask 1 ($50\%$): $1 \leq N \leq 20$, $1 \leq W \leq 1000$
• Subtask 2 ($50\%$): $1 \leq N \leq 100$, $1 \leq W \leq 10^6$

Example

3 50
10 60 
20 100 
30 120

220