Bookshelf 2 B

题目描述

Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $N(1\le N\le20)$ 头奶牛都有一个确定的身高 $H_i(1\le H_i\le1,000,000)$。设所有奶牛身高的和为 $S$。书架的高度为 $B$，并且保证 $1\le B\le S$。

为了够到书架顶，奶牛们需要选择若干头叠成一座奶牛塔，塔的高度等于所选奶牛身高之和。要求塔的高度不小于书架高度，并在满足要求的情况下尽可能低。

请计算奶牛塔最少比书架高多少。

输入格式

第一行包含两个整数 $N$ 和 $B$。

接下来 $N$ 行，每行一个整数 $H_i$，表示一头奶牛的身高。

输出格式

输出一个非负整数，表示奶牛塔最少比书架高的高度。

输入输出样例

5 16
3
1
3
5
6

1

说明

选择第 $1,3,4,5$ 头奶牛，总高度为：

不存在高度恰好为 $16$ 的方案，因此答案为：

数据范围

设所有奶牛身高之和为 $S$，保证：