题目描述

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

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

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

输入格式

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

$N$ $K$ $D$ $a_1$ $\ldots$ $a_N$

输出格式

答えを出力せよ。

题目大意

给定 $n$ 个数。现在可以从中选 $k$ 个数，需满足他们的和为 $d$ 的倍数。求最大和值。

translated by

4 2 2
1 2 3 4

6

3 1 2
1 3 5

-1

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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