Description
小明收到了一个朋友的求助,朋友开了一家运输公司,由于客户最近公司的业务很繁忙,目前公司只有一辆货车可供使用,这辆货车的最大载货量为C,而现在公司又收到了来自巨峡市的N个运输订单,第i个订单的货物重量为wi。朋友希望小明能够帮助他设计一个最优的运输方案,使得运输的货物总重量越大越好,并告诉他此次运输的货物总重量最大为多少。焦头烂额的小明把这个任务转交给了你。
例子:货车的最大载货量C=10,订单数量N=5,每个订单的货物重量分别为w1=7、w2=2、w3=6、w4=5、w5=4。
对于这个例子,最优的运输方案是运输第3和第5两个订单,此时运输的货物总重量为6+4=10。
而其他运输方案要么载货量小于上述方案的载货量10,不是最优的;要么载货量大于货车的最大载货量C,无法运输。
Input
输入由两行组成。
第一行2个数,分别表示N和C。(1<=N<=15)
第二行N个数,分别表示每个订单的货物重量wi。(1<=wi<=30)
Output
一个数,表示最优运输方案所运输的货物总重量。