QTKNAP - Túi Fibonacci
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 16 .
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 16 , 0≤V i ≤10 16 .
Output
Một dòng duy nhất là giá trị lớn nhất có thể lấy được.
Example
Input: 3 163 16 5 10 8 15 13 20 Output: 25
Lưu ý:
- Người up: code123