/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 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 と出力します。
Score : 400 points
Problem Statement
You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).
Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).
Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.
Constraints
- 1 \leq K \leq N \leq 100
- 1 \leq D \leq 100
- 0 \leq a_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K D a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
4 2 2 1 2 3 4
Sample Output 1
6
Here are all the ways to choose two terms in A.
- Choose a_1 and a_2, whose sum is 1+2=3.
- Choose a_1 and a_3, whose sum is 1+3=4.
- Choose a_1 and a_4, whose sum is 1+4=5.
- Choose a_2 and a_3, whose sum is 2+3=5.
- Choose a_2 and a_4, whose sum is 2+4=6.
- Choose a_3 and a_4, whose sum is 3+4=7.
Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.
Sample Input 2
3 1 2 1 3 5
Sample Output 2
-1
In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.