Cho $N$ đồ vật được đánh số từ $1$ đến $N$. Đồ vật thứ $i$ $(1\le i\le N)$ cho khối lượng là $w_i$ và giá trị là $v_i$

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là $W$, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là $W$

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N(1\le N\le 100)$ và $W(1\le W\le {10}^5)$: số lượng đồ vật và sức chứa tối đa của chiếc túi.

• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i(1\le w_i\le W)$ và $v_i(1\le v_i\le {10}^9)$ lần lượt là khối lượng và giá trị của đồ vật thứ $i$.

Dữ liệu ra

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input 1

3 8
3 30
4 50
5 60

Output 1

90