3486: 天平

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

天平

【问题描述】

一座天平有n个砝码,每个砝码的重量为Wi(longint以内),按重量从小到大排列,而且从第三个砝码开始,每个砝码重量至少为前两个砝码重量和,即Wi>=Wi-1 + Wi-2

天平的最大承受重量为C(longint以内),称重时选取若干个砝码放到天平上,这些砝码的重量和不能超过这个C。

求最大可以放置的砝码的重量和。

【文件输入】

第一行,两个用空格隔开的整数n,C;

接下来n行,每行有一个整数Wi。

【文件输出】

一个整数,代表最大组合重量

【输入样例】

3 15

1

10

20

【输出样例】

11

【数据规模】

对于20%数据,n<=16;

对于另外的30%数据,C<=100000;

对于100%的数据,n<=1000,C在longint以内

输入样例 复制


输出样例 复制


数据范围与提示