该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

余数配额

题目描述

有 $N$ 份材料，第 $i$ 份的价值为非负整数 $A_i$。需要从中选出恰好 $K$ 份不同的材料，使总价值除以 $D$ 的余数等于 $R$。

在满足条件的方案中，求最大的总价值。如果不存在这样的方案，输出 $-1$。材料按下标区分，价值相同的不同材料可以同时选择，每份材料至多选一次。

输入格式

第一行输入四个整数 $N,K,D,R$，其中 $1\le K\le N\le100$，$1\le D\le100$，$0\le R<D$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，其中 $0\le A_i\le10^9$。所有输入值均为整数。

输出格式

输出满足条件的最大总价值。如果无解，输出 $-1$。总价值为 $0$ 的合法方案应输出 $0$。

输入输出样例

输入 #1

4 2 3 1
1 2 4 6

输出 #1

10

输入 #2

3 2 2 1
2 4 6

输出 #2

-1

输入 #3

1 1 1 0
0

输出 #3

0

样例说明

样例 1 选择价值 $4,6$ 的材料，总价值为 $10$，且 $10\bmod3=1$。样例 2 任意两份材料的总价值均为偶数，无法满足余数为 $1$ 的要求。样例 3 必须选择唯一的材料，总价值 $0$ 合法。