Bookshelf 2

Farmer John recently bought another bookshelf for the cow library, but it is filling up quickly, and the only space left is at the very top.

FJ has $N$ cows ($1 \le N \le 20$), where cow $i$ has height $H_i$ ($1 \le H_i \le 1{,}000{,}000$ — these are very tall cows). The bookshelf has height $B$, with $1 \le B \le S$, where $S$ is the sum of the heights of all cows.

To reach the top of the bookshelf, one or more cows can stand on top of one another in a single stack, so that the stack's total height equals the sum of the heights of the cows in it. This total height must be at least $B$ for the cows to reach the top.

Because a stack taller than necessary is dangerous, find the set of cows that forms the shortest possible stack that still reaches the shelf. Print the minimal 'excess' height: the difference between the height of this optimal stack and the height of the bookshelf.

• Line 1: two space-separated integers, $N$ and $B$.
• Lines 2 to $N+1$: line $i+1$ contains a single integer $H_i$.

• A single integer: the non-negative difference between the total height of the optimal set of cows and the height of the bookshelf.

For example, using cows 1, 3, 4, and 5 gives a total height of $3 + 3 + 5 + 6 = 17$. A total height of exactly 16 cannot be formed, so the answer is $17 - 16 = 1$.