Subset Sum Closest to Target

You are given $N$ integers and an integer $K$. Your task is to select a subset of these numbers such that the sum of the selected numbers is as close as possible to $K$.

You need to output the sum of the chosen subset which minimizes the absolute difference $|\text{sum} - K|$. In case of a tie (i.e. two sums have the same absolute difference to $K$), output the smaller sum.

Note: The subset can be empty, in which case its sum is considered as 0.

inputFormat

The first line contains two space-separated integers: $N$ and $K$.

The second line contains $N$ space-separated integers representing the array elements.

outputFormat

Output a single integer which is the sum of the subset whose total is closest to $K$ as described above.

sample

4 10
1 3 4 8

9