Có \(N\) đồ vật được đánh số từ \(1\) đến \(N\). Đồ vật thứ \(i\) \((1 \le i \le N)\) có 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à.

Input

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\).

Output

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

Sample 1

Input

3 8
3 30
4 50
5 60

Output

90

Chọn đồ vật \(1\) và \(3\). Tổng khối lượng sẽ là \(3 + 5 = 8\) và tổng giá trị là \(30 + 60 = 90\).

Sample 2

Input

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Output

5000000000

Kết quả có thể vượt quá giới hạn kiểu số nguyên \(32\)-bit.

Sample 3

Input

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output

17

Chọn đồ vật \(2\), \(4\) và \(5\). Tổng khối lượng sẽ là \(5 + 6 + 3 = 14\) và tổng giá trị là \(6 + 6 + 5 = 17\).