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