Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QTKNAP - Túi Fibonacci

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qtknap


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≤1016.

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

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 ý:

Được gửi lên bởi:continue......
Ngày:2011-12-05
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC GAWK MAWK BC C-CLANG C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PYPY3 PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

hide comments
2011-12-16 17:30:34 Ðang tập code
Time chặt quá -((
2011-12-10 16:57:35 Nguyên
Topcoder SRM 352
2011-12-10 04:50:30 Cao Viên Viên
Khối lượng các túi có khác nhau không em ?
2011-12-06 07:37:54 continue......
mình đã hạ time xuống còn 0.5s để các bạn chú ý đến điều kiện fibonacci của đề bài
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.