Maximizing Representable Sums

Given a sequence of integers \(B_1, B_2, \dots, B_N\) and an integer \(K\), we say an integer \(M\) is representable if and only if there exists a selection of exactly \(K\) numbers \(A_1, A_2, \dots, A_K\) from the sequence (each number may be used at most once) such that

[ \sum_{i=1}^{K} A_i = M ]

You are allowed to modify exactly one element of the sequence (i.e. replace it with an arbitrary integer \(P\)). Your task is to choose one element to modify and decide its new value so that the total number of distinct representable integers \(M\) is maximized.

Note:

• If a representable sum can be obtained via subsets both including and not including the modified element, it is counted only once.
• You may choose any one element to modify and assign it any integer value.

inputFormat

The first line contains two integers \(N\) and \(K\) (with \(1 \le K \le N\)).

The second line contains \(N\) integers \(B_1, B_2, \dots, B_N\) separated by spaces.

outputFormat

Output a single integer representing the maximum number of distinct representable sums \(M\) that can be obtained after modifying exactly one element of the sequence.

sample

3 2
1 3 5

3