Maximum Consecutive Postage

You are given a set of n stamp denominations and an envelope limit k (i.e. at most k stamps can be used on an envelope). Using an unlimited supply of stamps in the given denominations, find the largest positive integer m such that every integer value from 1 to m can be represented as a sum of at most k stamps.

The problem can be formulated as follows:

Find the maximum positive integer \( m \) satisfying:

\[ \forall x\ (1 \le x \le m),\;\exists\; a_1, a_2, \dots, a_t \in S \text{ with } t \le k \text{ such that } a_1+a_2+\cdots+a_t=x, \]

where S is the set of available stamp denominations.

inputFormat

The first line contains two integers n and k separated by a space, where n is the number of stamp denominations and k is the maximum number of stamps allowed.

The second line contains n positive integers representing the available stamp denominations. The denominations are not necessarily sorted.

outputFormat

Output a single integer m, which is the maximum consecutive postage value starting from 1 that can be formed using at most k stamps. If 1 cannot be formed, output 0.

sample

3 3
1 3 5

11