P0847

[Usaco2005 Dec]Scales 天平

[Usaco2005 Dec]Scales 天平

约翰有一架用来称量奶牛体重的天平，以及 NN 个质量已知的砝码。称量时，他将奶牛放在天平的一侧，并在另一侧放置若干砝码，直至天平平衡。此时，所放砝码的总质量就是奶牛的质量。

天平每一侧所能承受的最大质量为 CC。如果某一侧物体的总质量大于 CC，天平就会损坏。

所有砝码已按质量从小到大排列。设第 ii 个砝码的质量为 wiw_i，则从第 33 个砝码开始，每个砝码的质量至少等于前两个砝码的质量之和，即：

wi≥wi−1+wi−2(3≤i≤N)。w_i\ge w_{i-1}+w_{i-2}\quad(3\le i\le N)。

请从这些砝码中选择若干个，使其总质量不超过 CC，并求出能够得到的最大总质量。

输入格式

第一行包含两个用空格分隔的正整数 NN 和 CC，分别表示砝码数量和天平每一侧所能承受的最大质量。

接下来 NN 行，每行包含一个正整数，表示一个砝码的质量。输入的砝码质量保证按不下降顺序排列。

输出格式

输出一个整数，表示不超过 CC 的最大砝码质量之和。

样例输入

3 15
1
10
20

样例输出

11

样例解释

共有 33 个砝码，质量分别为 11、1010 和 2020，天平每一侧最多承受质量 1515。

选择质量为 11 和 1010 的两个砝码，可以得到总质量 1111。其他砝码组合的总质量要么不超过 1111，要么超过天平的承重上限，因此答案为 1111。

数据范围

  • 1≤N≤10001\le N\le 1000；
  • 1≤C<2301\le C<2^{30}；
  • 每个砝码的质量均为正整数，且其数值可以用 3131 位二进制整数表示；
  • 砝码质量构成不下降序列；
  • 对于 3≤i≤N3\le i\le N，满足 wi≥wi−1+wi−2w_i\ge w_{i-1}+w_{i-2}。

来源与许可

本题为 USACO 2005 December 试题「Scales 天平」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 15
1
10
20

输出

11