题目描述

给出一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，求取出 $k$ 个不同的区间，要求满足取出区间的区间和是 $t$ 的倍数，求它们的区间和相加最大是多少？小可为了降低难度，规定对于每个下标来说，只能出现在右端点最多一次。

一个区间的区间和即里面所有数相加，例如 $a=[4,3,5]$，区间 $[1,2]$ 的和为 $7$，区间 $[1,3]$ 的和为 $12$。

保证至少存在 $k$ 个合法的区间。

输入格式

第一行三个正整数 $n, k, t$。

接下来一行 $n$ 个整数代表 $a_i$。

输出格式

输出一行一个数代表答案。

样例

4 3 2
2 3 5 3

20

样例说明

满足条件的区间有[1,3],[2,3],[3,4],[1,1]，对应的值是 $10、8、8、2$ ，但由于前两个区间的右端点下标都是 $3$ ，故只能选其中一个，肯定是保留区间 $[1,3]$ 更好，因为其值为 $10$ ，所以最终答案就是 $10+8+2 = 20$。

数据范围

前 $30\%$ 的数据，$1 \le n \le 100$

前 $60\%$ 的数据, $1 \le n \le 5000$

前 $100\%$ 的数据, $1 \le n, k, t, a_i \le 10^5$