最大倍数

题目描述

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

设 $S$ 为 $A$ 中 $K$ 个元素(下标互不相同)之和所能取到的非负整数的集合。

求 $S$ 中 $D$ 的倍数里的最大值。若 $S$ 中没有 $D$ 的倍数,则输出 -1。

输入格式

输入按以下格式从标准输入给出。

$N$ $K$ $D$
$a_1$ $\ldots$ $a_N$

输出格式

输出答案。

样例

4 2 2
1 2 3 4

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\}$。其中 $2$ 的倍数的最大值是 $6$,所以输出 $6$。

3 1 2
1 3 5

-1

在这个例子中,$S=\{1,3,5\}$。$S$ 中没有 $2$ 的倍数,所以输出 -1。

数据范围

• $1 \le K \le N \le 100$
• $1 \le D \le 100$
• $0 \le a_i \le 10^9$
• 输入中的所有值均为整数。