Maximizing Safe Addition on a k-bit Calculator

You are given a k-bit calculator that stores numbers as signed integers using k bits. In other words, the calculator can represent any number in the range \(\left[-2^{k-1},2^{k-1}\right)\). It is supposed to compute the sum of a sequence of n numbers \(a_1, a_2, \dots, a_n\) using the following pseudocode:

ans = 0
for each number x in an ordering of {a1, a2, ..., an}:
    if ans + x is not in \(\left[-2^{k-1},2^{k-1}\right)\):
        the calculator crashes
    else:
        ans = ans + x

By reordering the numbers you may avoid an overflow at some steps. However, it might be impossible to safely add all numbers. Your task is to select a subset of these numbers and a corresponding ordering so that the calculator will not overflow at any addition, and the total count of numbers added is maximized.

Note: The traditional ordering that guarantees the best chance of avoiding overflow is to add numbers with small magnitude first. In fact, if you separate the list into negatives, zeros, and positives then a safe strategy is to:

• Choose a set of negative numbers and order them in descending order (i.e. the ones closest to 0 first) so that the cumulative sum never drops below \(L=-2^{k-1}\).
• Include all zeros (they do not affect the sum).
• Choose a set of positive numbers and order them in ascending order so that when added after the negatives the cumulative sum never exceeds \(R=2^{k-1}-1\).

Formally, if you choose negatives with sum \(S_{neg}\) and positives with sum \(S_{pos}\) (zeros contribute 0), then the ordering (negatives first, then positives) is valid if and only if:

[ S_{neg} \ge L \quad \text{and} \quad S_{neg} + S_{pos} \le R. ]

Your goal is to maximize the total count of numbers (including zeros) that can be added safely.

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le 10^5,\, 1 \le k \le 64)\) — the number of numbers and the number of bits of the calculator.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \(\left(|a_i| \le 10^9\right)\), where \(a_i\) is the i-th number.

outputFormat

Output a single integer, the maximum count of numbers that can be summed up (in some order) without causing an overflow in the calculator.

sample

3 2
1 1 1

1