题目背景

译自 ICPC 2024 Yokohama Regional Contest。

题目描述

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$ $\cdots$ $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, \ldots, a_n$。其中，$a_i$（$0 \le a_i \le 10^8$）表示从顶部数第 $i$ 张钞票的面值。

输出格式

输出一行，包含你在婚礼仪式上礼金乘数的最大可能总和。

5 5 1
2 2 2 4 4

2

5 5 1
12 2 2 4 4

3

5 20000 10000
5000 10000 15000 5000 25000

2

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

2