Description

Farmer John recently added a huge bookshelf to the cows' library. Although it is very large, it was almost instantly filled with all kinds of books. Now, only a bit of space remains at the top of the shelf. All $N$ cows ($1 \le N \le 20$) each have a fixed height $H_i$ ($1 \le H_i \le 1{,}000{,}000$) (such tall cows >_<). Let the sum of all cow heights be $S$. The shelf height is $B$, and it is guaranteed that $1 \le B \le S$.

To reach the top of the shelf, which is higher than the tallest cow, the cows have to perform acrobatics: one stands on another's back, forming a “cow tower.” The height of the tower is the sum of the heights of the cows in it. To place items on the top of the shelf, the sum of the heights of the cows in the tower must be at least the shelf height.

The taller the tower, the more unstable it becomes, so the cows want to find a plan such that, among all towers with height at least $B$, the height is as small as possible. Your task is to write a program to compute, under this requirement, how much taller than the shelf the tower must be, minimized.

Input Format

Line $1$: Two space-separated integers: $N$ and $B$.

Lines $2$ to $N+1$: Line $i+1$ contains a single integer $H_i$.

Output Format

Line $1$: Output a non-negative integer, the minimal amount by which the tower’s height exceeds the shelf height.

5 16
3
1
3
5
6

1

Hint

We choose cows $1$, $3$, $4$, and $5$ to form a tower; their total height is $3+3+5+6=17$. No arrangement can form a tower of height $16$, so the answer is $1$.

Translated by ChatGPT 5