Peculiar Protocol

The Kingdom of Icpca has a peculiar protocol for wedding gifts. The gift amount must be a multiple of a fixed quantity plus a fixed extra. When the fixed quantity is $d$ and the fixed extra is $r$, the courteous amounts are $k \times d + r$ for any non-negative integer multiplier $k$.

You start with a pile of $n$ banknotes. Each time you attend a wedding ceremony, you draw a contiguous portion of the current pile whose sum is a courteous amount and give it as your gift. If no contiguous portion has such a sum, you cannot attend any more ceremonies. After drawing, the remaining banknotes are squeezed into a single pile, keeping their relative order. The new pile may contain a portion with a courteous sum, which lets you attend more ceremonies.

Your gifts raise your social reputation. Since the extra amount $r$ is mandatory, the multiplier $k$ is what matters. At each ceremony, your reputation rises in proportion to $k$.

For example, assume $d = 5$ and $r = 1$, and you have banknotes worth $2$, $2$, $2$, $4$, and $4$, in this order from the top. There are two ways to give a courteous gift.

• Give the first three banknotes, totaling $2 + 2 + 2 = 6 = 1 \times d + r$. The remaining banknotes are $4$ and $4$. No contiguous portion of them sums to a courteous amount, so you cannot attend any more ceremonies.
• Give the third and fourth banknotes, totaling $2 + 4 = 6 = 1 \times d + r$. The remaining banknotes are $2$, $2$, and $4$, in this order. The second and third banknotes total $2 + 4 = 6 = 1 \times d + r$, so you can attend another ceremony.

In this example, the second way maximizes your reputation with two ceremonies, because the multipliers sum to $1 + 1 = 2$, the largest possible total.

By contrast, if the first banknote is worth $12$, giving the first three banknotes stops you from attending more ceremonies. That method still maximizes your reputation, because its multipliers sum to $3$.

Compute the maximum possible total of the multipliers from your wedding gifts. Assume you have enough unmarried relatives and friends to attend as many ceremonies as you can give courteous gifts to.

The first line contains three integers $n$, $d$, and $r$. The integer $n$ ($1 \le n \le 500$) is the number of banknotes. The integers $d$ and $r$ ($2 \le d \le 10^8$, $0 \le r < d$) are the parameters of the protocol.

The second line contains $n$ integers $a_1, \dots, a_n$ ($0 \le a_i \le 10^8$), where $a_i$ is the value of the banknote that is $i$-th from the top.

Print a single line containing the maximum possible total of the multipliers.