Giải bài trực tuyến

Hè vừa rồi các bạn trường xyz tổ chức một buổi đi chơi và tham quan ở một địa điểm đó là ...... Sa-ha-ra (sa mạc lớn nhất thế giới) để tìm hiểu về các địa danh trên thế giới. Trời rất nóng bức nên các bạn đều khát nước, vì vậy một số bạn quyết định đi tìm nước, và may mắn họ đã tìm thấy một ốc đảo. Tuy nhiên ốc đảo ấy lại không có nước mà thay vào đó là một kho báu của Paraong để lại. Trong kho báu đó có rất nhiều loại như vàng, bạc, đã quý, kim cương,....(những vật có giá trị) hoặc đá, sỏi, cát,..(nhưng vật không có giá trị). Vì sự tò mò các bạn ấy đã quyết định trộm một ít về. Tuy nhiên họ chỉ có 1 cái túi rất "bé" nên chỉ chứa đc một số lượng kho báu nhất định. Và các bạn ấy đang cố tính toán xem cần phải lấy làm sao để được giá trị là lớn nhất. Điều đặc biệt ở đây là ai cập rất giỏi về toán học nên khối lượng của các vật trong kho báu đều là một số fibonacci. Nếu là bạn, bạn sẽ tính được không ???

Yêu cầu: cho khối lượng lớn nhất có thể bỏ vào túi, khối lượng và giá trị của các vật trong kho báu ( các vật rất cứng và không thể đập bể ra mà phải trọn nguyên cả vật ). Hãy tính giá trị lớn nhất mà các bạn ấy có được.

Input

Dòng đầu tiên: N (số loại vật trong kho báu), M (khối lượng lớn nhất có thể bỏ vào túi): N≤70, 0≤M≤10¹⁶.

Dòng thứ i trong N dòng tiếp theo gồm 2 số: W_i (khối lượng của vật trong kho báu), V_i (giá trị của vật): 0≤W_i≤10¹⁶, 0≤V_i ≤10¹⁶.

Output

Một dòng duy nhất là giá trị lớn nhất có thể lấy được.

Example

Input:
3 16
3 16

5 10

8 15

13 20
Output:
25

Lưu ý: