AT_abc281_d [ABC281D] Max Multiple

题目描述

给定一个非负整数列 $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\}$。$S$ 中是 $2$ 的倍数的最大值为 $6$，所以输出 $6$。

样例解释 2

本例中 $S=\{1,3,5\}$。$S$ 中没有任何 $2$ 的倍数，因此输出 $-1$。

由 ChatGPT 4.1 翻译