题目描述

有一个行李箱，最多可以容纳 $C$ 公斤的行李，有 $N$ 件行李，第 $i$ 件行李的重量为 $W_i$ 公斤。

请设计一种方案，挑选一些行李装到箱子里，尽可能地将箱子填满。

输出箱子空余重量的最小值。

（请注意这题与《消磨时间》题面基本相同，区别在于数据范围）

输入格式

• 第一行：两个整数表示 $N$ 与 $C$。
• 第二行到第 $N+1$ 行：$N$ 个整数表示 $W_1,W_2,\cdots,W_N$

输出格式

4 10
9 
3 
2 
4

1

样例解释 1

10-(2+3+4)=1

数据范围

• $30\%$ 的数据，$1\leq N\leq 20$
• $60\%$ 的数据，$1\leq N\leq 100$
• $100\%$ 的数据，$1\leq N\leq 500$
• $1\leq C< 100,000$
• $1\leq W_i< 100,000$