102813: [AtCoder]ABC281 D - Max Multiple

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.

问题描述

给你一个非负整数序列$A=(a_1,a_2,\ldots,a_N)$。

让$S$为$A$中$K$个项（下标不同）之和的所有非负整数的集合。

找出$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$中选择两项的方法。

• 选择$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。