atcoder#ABC281D. [ABC281D] Max Multiple

[ABC281D] Max Multiple

题目描述

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

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

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

输入格式

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

N N K K D D a1 a_1 \ldots aN a_N

输出格式

答えを出力せよ。

题目大意

给定 nn 个数。现在可以从中选 kk 个数,需满足他们的和为 dd 的倍数。求最大和值。

translated by

https://www.luogu.com.cn/user/367488

4 2 2
1 2 3 4
6
3 1 2
1 3 5
-1

提示

制約

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

Sample Explanation 1

A A から 2 2 個の項を選ぶ方法を列挙すると - a1 a_1 a2 a_2 を選ぶ。選ばれた項の和は 1+2=3 1+2=3 となる。 - a1 a_1 a3 a_3 を選ぶ。選ばれた項の和は 1+3=4 1+3=4 となる。 - a1 a_1 a4 a_4 を選ぶ。選ばれた項の和は 1+4=5 1+4=5 となる。 - a2 a_2 a3 a_3 を選ぶ。選ばれた項の和は 2+3=5 2+3=5 となる。 - a2 a_2 a4 a_4 を選ぶ。選ばれた項の和は 2+4=6 2+4=6 となる。 - a3 a_3 a4 a_4 を選ぶ。選ばれた項の和は 3+4=7 3+4=7 となる。 となり、S={3,4,5,6,7} S=\{3,4,5,6,7\} となります。S S に含まれる 2 2 の倍数のうち最大のものは 6 6 なので、6 6 と出力します。

Sample Explanation 2

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