#12 「 Yuno like cake 」

统计

双十一就要来啦!而 Yuno 刚刚获得了一笔 $X$ 元的奖金。那么是不是应该清空下购物车呢?

购物车总共有 $N$ 个物品,每个物品的价格为 $V_i$,Yuno 想尽可能地把手头的奖金给花光,所以她要精心选择一些商品,使得其价格总和最接近但又不会超过奖金的金额。那么 Yuno 最后最少可以剩下多少钱呢?

输入格式

第一行,两个正整数 $N,X$。

第二行,$N$ 个正整数 $V_i$ 表示第 $i$ 个物品的价格。

输出格式

输出一个整数,表示 Yuno 最后最少可以剩下的钱数。

样例数据

input1

4 50
1 2 3 4

output1

40

input2

4 5
1 2 3 4

output2

0

数据规模与约定

$N\le 40,~X,V_i\le10^9$

时间限制:1s

空间限制:512MB

Author: NanoApe