P2662 [WC2002] Cattle Farm Fence

With the help of “nimeng” (泥萌), Xiao L successfully solved the problem of modifying binary trees. He then wrote a paper and was directly admitted to “Cha Yuan” (叉院). Envious? Diligent and thoughtful, he later switched fields in graduate school and entered the Guanghua School of Management at Peking University. After graduation, with his strong background in economics and computer science, he built a modern dairy farm.

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!

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 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`.

- 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