Maximizing Distinct Weights Measurement

You are given a collection of n weights with weights \(a_i\) (\(1 \leq i \leq n\)). You are allowed to remove exactly m weights. After removal, you have a set of \(n-m\) weights. These weights can only be placed on one side of a balance scale. Your task is to determine the maximum number of different positive weights (i.e. sums, not including 0) that can be measured by selecting any non-empty subset of the remaining weights.

Formally, if you select a set \(S\) of \(n-m\) weights, let \(F(S)\) denote the set of all sums produced by taking a non-empty subset of \(S\). You need to choose which m weights to remove from the original \(n\) weights so that \(|F(S)|\) is maximized.

Note: The same weight value may appear multiple times. Use \(\LaTeX\) format for any formulas.

Constraints (for this problem):

• \(1 \leq n \leq 15\)
• \(0 \leq m < n\)
• \(1 \leq a_i \leq 10^9\)

It is guaranteed that the input values are chosen such that a brute force solution over all combinations of \(n-m\) weights is feasible.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), representing the weights.

outputFormat

Output a single integer, which is the maximum number of distinct positive weights that can be measured using the optimal set of \(n-m\) weights.

sample

3 1
1 2 3

3