Closest Subsequence Sum

You may delete any elements, including all or none of them; find the minimum absolute difference between the sum of the remaining subsequence and goal. Negative numbers and the empty subsequence are allowed.

输入格式

The first line contains n goal, and the second line contains n integers. 1≤n≤40, −10⁷≤nums[i]≤10⁷, −10⁹≤goal≤10⁹.

输出格式

Output the minimum absolute difference.

样例 1

输入：

4 6
5 -7 3 5

输出：

0

样例 2

输入：

4 -5
7 -9 15 -2

输出：

1

样例 3

输入：

3 -7
1 2 3

输出：

7

样例说明

The answers are 0, 1, and 7 in order; the third example requires allowing the empty subsequence.