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$

输出格式

输出答案。

4 2 2
1 2 3 4

6

3 1 2
1 3 5

-1

提示

$1 \leq K \leq N \leq 100$ $1 \leq D \leq 100$ $0 \leq a_i \leq 10^9$ 输入中的所有值均为整数。下面列出了从 $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$。
在这个例子中，我们有 $S=\{1,3,5\}$。$S$ 中没有 $2$ 的倍数，所以你应当输出 $-1$。

标签: AtCoder|abc281D

来源

AtCoder|abc281D