Description

The cows are very clever, so when building the fence they decided to compete with Xiao L in wits. Xiao L has $N$ types of lumber available for building fences, with lengths $l_1, l_2, \dots, l_N$. Each type is available in unlimited quantity.

During construction, he will join all selected pieces end to end, so the fence length equals the sum of the lengths of the pieces he uses. However, Xiao L soon realized that many target lengths cannot be obtained by summing these lumber lengths, so he decided that, when necessary, he would cut some lumber shorter before use.

Since Xiao L is thrifty, he set a rule for himself: any single piece may be shortened by at most $M$ meters. The amount cut from each piece does not need to be the same. Due to primitive measuring tools, he can only cut an integer number of meters. Therefore, if he has two types of lumber with lengths $7$ and $11$, and each piece can be cut by at most $1$ meter, then in effect there are $4$ usable lengths: $6, 7, 10, 11$.

Believing his cows are unrivaled, he let them design the fence themselves. The cows want to avoid being constrained by the fence during play, so they try to make things difficult for Xiao L by choosing a fence length such that, no matter how he processes the lumber, the sum of lengths can never equal their designed total. But Xiao L knows that if the fence length is too small, he can quickly determine it is impossible to build. Thus, he wants your help to find the maximum fence length that cannot be constructed.

Surely this won’t stump you. If you can help Xiao L solve this problem, he might even give you $\frac{1}{8}$ of his final assets!

Input Format

The first line contains two integers $N, M$, the number of lumber types and the maximum amount each piece can be shortened.

The next $N$ lines each contain an integer $l_i$ ($1 < l_i < 3000$), the original length of the $i$-th type of lumber.

Output Format

Output a single integer: the maximum fence length that cannot be constructed. If every fence length can be constructed or this maximum does not exist, output -1.

2 1
7
11

15

Hint

• For $40\%$ of the testdata, $1 < N < 10$, $0 \le M < 300$.
• For $100\%$ of the testdata, $1 < N < 100$, $0 \le M < 3000$.

Translated by ChatGPT 5