Minimizing Excess Height of the Cow Tower

Farmer John recently added a huge bookshelf to the cow library. Although the bookshelf is enormous, it was filled almost instantly with books of every kind. Now, only a little space remains at the top of the shelf. All N cows (with N between 1 and 20) have known heights \(H_i\) (with \(1 \le H_i \le 1\,000\,000\)), and let \(S = \sum_{i=1}^{N} H_i\) be the total height of all cows. The bookshelf has a height \(B\) (where \(1 \le B \le S\)).

To reach the top of the shelf, which is above the height of the tallest cow, the cows form a tower by standing on each other's backs. The total height of the tower is simply the sum of the heights of the cows in the tower. In order to place something on the top of the shelf, the tower's height must be at least \(B\). However, the taller the tower, the more unstable it becomes. Therefore, the cows want to build a tower which is at least as tall as the bookshelf, but as close as possible to \(B\) so as to minimize the extra height. Your task is to compute the minimum extra height above \(B\) that the cows must achieve, i.e. if the optimal tower has height \(H\), output \(H - B\).

inputFormat

The input consists of multiple lines. The first line contains two integers \(N\) and \(B\) separated by a space. The following \(N\) lines each contain one integer representing the height \(H_i\) of each cow.

outputFormat

Output a single integer representing the minimum excess height of the tower over \(B\) such that the total height is at least \(B\).

sample

3 8
3
5
3

0