配点 : $400$ 点

問題文

非負整数列 $A=(a_1,a_2,\ldots,a_N)$ が与えられます。

$A$ の(添え字が相異なる) $K$ 個の項の和として考えられる非負整数の集合を $S$ とします。

$S$ に含まれる $D$ の倍数の最大値を求めてください。ただし、$S$ に $D$ の倍数が含まれない場合、代わりに -1 と出力してください。

制約

• $1 \leq K \leq N \leq 100$
• $1 \leq D \leq 100$
• $0 \leq a_i \leq 10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $D$

$a_1$ $\ldots$ $a_N$

出力

答えを出力せよ。

4 2 2
1 2 3 4

6

$A$ から $2$ 個の項を選ぶ方法を列挙すると

• $a_1$ と $a_2$ を選ぶ。選ばれた項の和は $1+2=3$ となる。
• $a_1$ と $a_3$ を選ぶ。選ばれた項の和は $1+3=4$ となる。
• $a_1$ と $a_4$ を選ぶ。選ばれた項の和は $1+4=5$ となる。
• $a_2$ と $a_3$ を選ぶ。選ばれた項の和は $2+3=5$ となる。
• $a_2$ と $a_4$ を選ぶ。選ばれた項の和は $2+4=6$ となる。
• $a_3$ と $a_4$ を選ぶ。選ばれた項の和は $3+4=7$ となる。

となり、$S=\{3,4,5,6,7\}$ となります。$S$ に含まれる $2$ の倍数のうち最大のものは $6$ なので、$6$ と出力します。

3 1 2
1 3 5

-1

この例では $S=\{1,3,5\}$ です。$S$ に含まれる非負整数はいずれも $2$ の倍数でないため、-1 と出力します。