OI题库

有何不可(why.in/why.out)

陈立杰 灰色头像模拟赛 P4

引子： 为你唱这首歌 没有什么风格
它仅仅代表着 我想给你快乐
为你解冻冰河 为你做一只扑火的飞蛾
没有什么事情是不值得
为你唱这首歌 没有什么风格
它仅仅代表着 我希望你快乐
为你辗转反侧 为你放弃世界有何不可
夏末秋凉里带一点温热 有换季的颜色

背景：某天，WJMZBMR在外面闲逛，看到神牛XXX在跟他的GF（你们懂的）逛街。他的GF看中了N件物品，每件物品有价格和喜爱度，

可WJMZBMR知道XXX不是神马富二代。 XXX身上一分钱都没有（全被他GF花光了）。XXX非常的痛苦的时候，被春哥看到了，春哥正好心情很好，

看在XXX平时信春哥的份上，给了XXX M元钱。 同时那天是伟大的数学家Fibonacci的生日，所以所有商品的价格全部是Fibonacci数。

XXX很爱他的GF，他希望在自己能及的范围内让买来的物品的喜爱度最大。 WJMZBMR在旁边表示压力很大囧。。。

数学定义：
Fibonacci数列：满足a[1]=1,a[2]=1,a[n]=a[n-1]+a[n-2]的数列。

前几项为1,1,2,3,5,8,13 Fibonacci数：Fibonacci数列中的数

N个物品，体积都是Fibonacci数，价值也给出，每个物品只有一个，放入体积为M的背包中，求最大价值。

01背包问题的扩展

输入：

第一行N和M表示物品数和钱数

接下来N行，每行两个数分别表示一个物品的价格和喜爱度

输出：

一行表示最大价值

样例输入：

3 10
1 3
5 8
8 10

样例输出：

13

样例的解释：
选择第一个和第三个物品

数据范围：
100%的数据 N<=200
40%的数据 M<=10000
100%的数据 M<=10^9
物品重量价值，可以用int和longint存储，但是总价值/总重量说不定就溢出了