Background

Upright people, strong and unyielding people, people who are fair and honest.

Such people probably suffer losses everywhere, but this view is probably seen from the eyes of cheaters. Upright people, even after death, are still the most respected.

Problem Description

There is a calculator that uses a $k$-bit signed integer type to store numbers. That is, the range a variable can represent is $[-2^{k-1},2^{k-1})$. Now we want to use this calculator to compute the sum of a sequence of numbers $a_1,a_2,\cdots,a_n$. The pseudocode is as follows:

Because of a strange property, if the result of adding two variables falls outside $[-2^{k-1},2^{k-1})$, that is, an overflow happens, then this calculator will freeze and can never compute again.

To prevent this, a workaround is to change the order of the $a_i$. It is easy to see that this will not change the final sum.

However, there may be no ordering that allows the computer to finish summing all $n$ numbers without crashing. Still, we hope to compute the sum of as many numbers as possible.

Input Format

The first line contains two integers $n,k$, representing the number of elements and the integer bit width.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$.

Output Format

Output one integer in a single line, meaning the maximum number of values whose sum can be computed.

3 3
1 2 3

2

10 4
-3 5 6 -4 5 3 -4 1 -1 0

9

Hint

Sample Explanation

• For sample $1$, one optimal plan is $[a_1,a_2,a_3]$, so that there is no overflow when computing the first two numbers.
• For sample $2$, one optimal plan is $[a_{10},a_1,a_2,a_5,a_4,a_7,a_6,a_8,a_9,a_3]$, so that there is no overflow when computing the first $9$ numbers.

Constraints and Notes

For all testdata, it is guaranteed that $1\le n\le 500$, $1< k\le 8$, $-2^{k-1}\le a_i<2^{k-1}$.

Translated by ChatGPT 5