当前没有测试数据。

D-最大倍数

分值：400分

问题描述

给定一个非负整数序列 $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$中选择两项的方式：

1. 选择 $a_1$ 和 $a_2$，它们的和是 $1+2=3$。
2. 选择 $a_1$ 和 $a_3$，它们的和是 $1+3=4$。
3. 选择 $a_1$ 和 $a_4$，它们的和是 $1+4=5$。
4. 选择 $a_2$ 和 $a_3$，它们的和是 $2+3=5$。
5. 选择 $a_2$ 和 $a_4$，它们的和是 $2+4=6$。
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。