Icpca 王国在婚礼仪式上有一种独特的礼金习俗。礼金金额必须是某个固定数量的倍数加上一个固定的余数。当固定数量为 $d$ 且固定余数为 $r$ 时，合乎礼仪的礼金金额为 $k \times d + r$，其中 $k$ 为任意非负整数。

起初，你有一叠共 $n$ 张钞票。每次参加婚礼时，你都会从当前的钞票堆中取出一部分连续的钞票作为礼金，其总额必须是一个合乎礼仪的金额，即 $d$ 的倍数加上 $r$。如果没有连续的部分能凑出这样的金额，你就无法再参加婚礼了。取出钞票后，剩余的钞票会合并成新的一叠，并保持它们原有的相对顺序。合并后的钞票堆中可能再次出现符合条件的连续部分，从而让你能够参加更多的婚礼。

你的礼金旨在提升社会声望。由于额外金额 $r$ 被视为强制性的，因此乘数 $k$ 被视为衡量声望的关键。你在每次参加婚礼时获得的声望提升与该次礼金的乘数 $k$ 成正比。

例如，假设 $d = 5$，$r = 1$，你拥有的钞票面值依次为 2, 2, 2, 4, 4。当你参加婚礼时，有两种可能的礼金给付方式：

• 取出前三张钞票作为礼金，总额为 $2 + 2 + 2 = 6 = 1 \times d + r$。取出后，剩余钞票面值为 4 和 4。剩余钞票中没有连续部分的总和是合乎礼仪的金额。因此，你无法再参加婚礼。
• 取出第三和第四张钞票作为礼金，总额为 $2 + 4 = 6 = 1 \times d + r$。取出后，剩余钞票面值依次为 2, 2, 4。你可以参加另一场婚礼，因为第二和第三张钞票的总和为 $2 + 4 = 6 = 1 \times d + r$，符合礼仪。

在这个例子中，第二种方式通过参加两场婚礼使你的社会声望最大化，因为乘数之和为 $1 + 1 = 2$，达到了最大可能值。

相比之下，如果第一张钞票的面值是 12，在仪式上取出前三张钞票会使你无法参加后续的婚礼。然而，这却能使你的社会声望最大化，因为乘数之和为 3，达到了最大可能值。

请计算你在婚礼上给出的礼金所能获得的最大乘数总和。你可以假设你有足够多的未婚亲友，只要你能给出合乎礼仪的礼金，就可以参加任意数量的婚礼。

输入格式

输入包含单个测试用例，格式如下：

$n$ $d$ $r$ $a_1$ $\dots$ $a_n$

第一行包含三个整数 $n$、$d$ 和 $r$。整数 $n$ ($1 \le n \le 500$) 是你拥有的钞票数量。整数 $d$ 和 $r$ ($2 \le d \le 10^8$, $0 \le r < d$) 代表该独特习俗的参数。第二行包含 $n$ 个整数 $a_1, \dots, a_n$。其中 $a_i$ ($0 \le a_i \le 10^8$) 表示从上往下数第 $i$ 张钞票的面值。

输出格式

输出一行，包含你在婚礼上给出的礼金所能获得的最大乘数总和。

样例

输入 1

5 5 1
2 2 2 4 4

输出 1

2

输入 2

5 5 1
12 2 2 4 4

输出 2

3

输入 3

5 20000 10000
5000 10000 15000 5000 25000

输出 3

2

输入 4

9 5 3
4 2 2 1 1 4 3 2 1

输出 4

2