题目描述

小可参加了一个超市的抽奖活动。活动有 $n$ 张不同的卡片，每张卡片上有一个积分值。

活动规则如下：

1. 小可需要恰好选择 $m$ 张卡片
2. 选出的卡片积分总和必须是 $d$ 的倍数
3. 在满足前两个条件的前提下，积分总和要尽可能大

如果无法找到满足条件的 $m$ 张卡片，则挑战失败。

输入格式

第一行三个整数 $n, m, d$：

• $n$：卡片总数
• $m$：需要选择的卡片数量
• $d$：倍数要求

第二行 $n$ 个整数 $v_1, v_2, \dots, v_n$，表示每张卡片的积分值。

输出格式

输出一个整数，表示满足条件的最大积分总和。

如果无法满足条件，输出 -1。

样例

4 2 2
1 2 3 4

6

3 1 2
1 3 5

-1

6 3 5
2 6 9 1 13 3

25

数据范围

对于 $30\%$ 的数据，$1\le m\le n\le 25$ 。

对于 $100\%$ 的数据，$1\le m\le n\le 100$，$1\le d\le 100$，$0\le v_i\le 10^9$。