Description

There are $n$ weights with masses $a_i$. After removing exactly $m$ weights, ask for the maximum number of different measurable weights (excluding $0$).

Note that weights can only be placed on one side of the balance.

Input Format

The first line contains two integers $n$ and $m$, separated by a space.

The second line contains $n$ positive integers $a_1, a_2, a_3, \ldots, a_n$, representing each weight’s mass.

Output Format

Output a single integer: the maximum number of different measurable weights.

3 1
1 2 2

3

Hint

[Sample Explanation]

After removing one weight of $2$, you can measure $1, 2, 3$, for a total of $3$ distinct weights.

[Constraints]

• For $20\%$ of the testdata, $m = 0$.
• For $50\%$ of the testdata, $m \leq 1$.
• For $50\%$ of the testdata, $n \leq 10$.
• For $100\%$ of the testdata, $n \leq 20$, $m \leq 4$, $m < n$, $a_i \leq 100$.

Translated by ChatGPT 5