Bookshelf 2

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 20 cow heights and a target bookshelf height B, find the minimum amount by which some subset's total height exceeds or equals B.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation, Array, Greedy
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Note

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$ .

Examples4

Example 1
Input
```
5 16
3
1
3
5
6
```
Expected output
```
1
```
Example 2
Input
```
1 1
1
```
Expected output
```
0
```
Example 3
Input
```
1 5
10
```
Expected output
```
5
```
Example 4
Input
```
3 6
1
2
3
```
Expected output
```
0
```