题目描述

给定一个长度为 $N$ 的非负整数序列：

定义集合 $S$ 为所有可以通过从 $A$ 中选取恰好 $K$ 个不同下标的元素之和得到的整数集合。

请你从 $S$ 中找出所有是 $D$ 的倍数的数中的最大值。

如果不存在这样的数，则输出 $-1$。

输入格式

N K D
a_1 a_2 ... a_N

输出格式

输出一个整数，表示答案。

数据范围与子任务

• 所有输入均为整数

子任务

• 子任务 1（20%）

  • $1 \le N \le 20$

• 子任务 2（30%）

  • $1 \le N \le 100$
  • $D \le 10$

• 子任务 3（50%）

  • $1 \le K \le N \le 100$
  • $1 \le D \le 100$
  • $0 \le a_i \le 10^9$

样例

输入 1

4 2 2
1 2 3 4

输出 1

6

输入 2

3 1 2
1 3 5

输出 2

-1