Có ~N~ viên đá quý được đánh số từ 1 đến ~N~. Viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~ và giá trị là ~v_i~.

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để 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ị lớn nhất của các viên đá mà Nam có thể mang về nhà. Biết rằng Nam được lấy một phần của viên đá.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 10^5~) và ~W~ (~1 ≤ W ≤ 10^3~): số lượng viên đá 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 ≤ w_i ≤ W~) và ~v_i~ (~1 ≤ v_i ≤ 10^9~) — lần lượt là khối lượng và giá trị của viên đá thứ ~i~.

Output

• Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà. Kết quả làm tròn đến số nguyên.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

98

Giải thích:

Chọn viên đá thứ hai và 4/5 phần viên đá thứ 3, chúng có trọng lượng là 4 + 5 * 4/5 = 8 vừa với chiếc túi và giá trị là 50 + 60 * 4/5 = 98.

Có ~N~ viên đá quý được đánh số từ 1 đến ~N~. Viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~ và giá trị là ~v_i~.

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để 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ị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 100~) và ~W~ (~1 ≤ W ≤ 10^5~): số lượng viên đá 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 ≤ w_i ≤ W~) và ~v_i~ (~1 ≤ v_i ≤ 10^9~) — lần lượt là khối lượng và giá trị của viên đá thứ ~i~.

Output

• Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

90

Giải thích:

Chọn viên đá thứ nhất và thứ 3, chúng có trọng lượng là 3+5=8 vừa với chiếc túi và giá trị là 30+60=90.

Có ~N~ loại viên đá quý được đánh số từ 1 đến ~N~. Loại viên thứ ~i~ (~1 ≤ i ≤ N~) có khối lượng là ~w_i~, giá trị là ~v_i~ và số lượng rất lớn, được xem như là vô hạn.

Nam định chọn một số viên bỏ vào chiếc túi của anh ta để 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ị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ (~1 ≤ N ≤ 100~) và ~W~ (~1 ≤ W ≤ 10^3~): số lượng loại đá 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 ≤ w_i ≤ W~) và ~v_i~ (~1 ≤ v_i ≤ 10^9~) - lần lượt là khối lượng và giá trị của loại viên đá thứ ~i~.

Output

• Xuất ra tổng giá trị lớn nhất của các viên đá mà Nam có thể mang về nhà.

Ví dụ

Input

3 8
3 30
4 50
5 60

Output

100

Giải thích:

Chọn 2 viên đá loại 2, chúng có trọng lượng là 4 * 2=8 vừa với chiếc túi và giá trị là 50 * 2=100.

Cho dãy số gồm các số nguyên dương từ ~1~ đến ~N~, viết theo thứ tự tăng dần. Ta thực hiện liên tiếp các lượt xoá như sau:

• Lượt 1: đếm từ trái sang phải và xoá các số ở vị trí lẻ trong dãy hiện tại.
• Lượt 2: trên dãy còn lại, đếm từ phải sang trái và xoá các số ở vị trí chẵn.
• Lượt 3: trên dãy còn lại, đếm từ trái sang phải và xoá các số ở vị trí lẻ.
• Lượt 4: trên dãy còn lại, đếm từ phải sang trái và xoá các số ở vị trí chẵn.
• ...
• Cứ tiếp tục quy luật như vậy cho đến khi trong dãy chỉ còn lại đúng ~1~ số.

Yêu cầu: Hãy xác định số cuối cùng còn lại trong dãy.

Dữ liệu nhập vào từ bàn phím

Gồm một dòng duy nhất chứa số tự nhiên ~N~ <= 10^12.

Kết quả ghi ra màn hình

In ra một số tự nhiên duy nhất là số cuối cùng còn lại.

Ví dụ

Input

10

Output

6

Giải thích VD:

• Ban đầu, dãy a là 1, 2, 3, 4, 5, 6, 7 ,8, 9, 10
• Lượt 1 xoá các số 1, 3, 5, 7, 9; dãy a còn lại là 2, 4, 6, 8, 10
• Lượt 2 xoá các số: 8, 4; dãy a thành 2, 6, 10
• Lượt 3 xoá các số: 2, 10; dãy a còn 1 số 6