atcoder#ABC281D. [ABC281D] Max Multiple

[ABC281D] Max Multiple

配点 : 400400

問題文

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

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

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

制約

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

入力

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

NN KK DD

a1a_1 \ldots aNa_N

出力

答えを出力せよ。

4 2 2
1 2 3 4
6

AA から 22 個の項を選ぶ方法を列挙すると

  • a1a_1a2a_2 を選ぶ。選ばれた項の和は 1+2=31+2=3 となる。
  • a1a_1a3a_3 を選ぶ。選ばれた項の和は 1+3=41+3=4 となる。
  • a1a_1a4a_4 を選ぶ。選ばれた項の和は 1+4=51+4=5 となる。
  • a2a_2a3a_3 を選ぶ。選ばれた項の和は 2+3=52+3=5 となる。
  • a2a_2a4a_4 を選ぶ。選ばれた項の和は 2+4=62+4=6 となる。
  • a3a_3a4a_4 を選ぶ。選ばれた項の和は 3+4=73+4=7 となる。

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

3 1 2
1 3 5
-1

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