题目描述

给定 $n$ 个数。现在可以从中选 $k$ 个数，需满足他们的和为 $d$ 的倍数。求最大和值。

输入格式

第一行输入三个整数 $n, k, d$ 。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n$ 。

输出格式

输出题目要求的答案。

样例 #1

样例输入 #1

4 2 2
1 2 3 4

样例输出 #1

6

选 $2$ 个数的总和有 $(3,4,5,6,7)$ ，其中 $6$ 是 $2$ 的最大倍数，输出 $6$ 。

样例 #2

样例输入 #2

3 1 2
1 3 5

样例输出 #2

-1

选 $1$ 个数的总和有 $(1,3,5)$ 三种可能，没有一种是 $2$ 的倍数，输出 $-1$ 。

提示

对于 $100\%$ 的数据：

• $1\ \leq\ K\ \leq\ N\ \leq\ 100$
• $1\ \leq\ D\ \leq\ 100$
• $0\ \leq\ a_i\ \leq\ 10^9$
• 所有的输入都是整数。