問題文

非負整数列 $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$

出力

答えを出力せよ。

入力例 1

4 2 2
1 2 3 4

出力例 1

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$ と出力します。

入力例 2

3 1 2
1 3 5

出力例 2

-1

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