[ABC281D] 最大倍数

题目描述

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

设 $S$ 为从 $A$ 中选取（下标不同的）$K$ 个项的和所构成的非负整数集合。

请找出 $S$ 中能被 $D$ 整除的最大数。若 $S$ 中不存在 $D$ 的倍数，则输出 -1。

输入格式

输入通过标准输入按以下形式给出：

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

输出格式

输出答案。

输入输出样例 #1

输入 #1

4 2 2
1 2 3 4

输出 #1

6

输入输出样例 #2

输入 #2

3 1 2
1 3 5

输出 #2

-1

说明/提示

限制条件

• $1 \leq K \leq N \leq 100$
• $1 \leq D \leq 100$
• $0 \leq a_i \leq 10^9$
• 输入均为整数

样例解释 1

列举从 $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\}$，其中能被 $2$ 整除的最大数是 $6$，故输出 $6$。

样例解释 2

在此例中 $S=\{1,3,5\}$，集合中所有数均不能被 $2$ 整除，因此输出 -1。