특이한 축의금 규칙

Icpca 왕국에는 결혼식 축의금에 관한 특이한 규칙이 있다. 축의금 액수는 고정된 값 $d$의 배수에 고정된 값 $r$을 더한 값이어야 한다. 즉 $d$를 고정 단위, $r$을 고정 추가액이라 하면, 적절한 축의금 액수는 0 이상의 정수 $k$에 대해 $k \times d + r$로 나타낼 수 있는 금액이다.

처음에 지폐 $n$장이 쌓여 있다. 결혼식에 참석할 때마다 현재 지폐 더미에서 연속된 구간을 골라, 그 합이 적절한 액수가 되도록 뽑아서 축의금으로 낸다. 그런 구간이 없으면 더 이상 결혼식에 참석할 수 없다. 뽑고 남은 지폐는 순서를 유지한 채 하나의 더미로 합쳐진다. 남은 더미에 적절한 합을 가진 구간이 있으면 결혼식에 더 참석할 수 있다.

축의금은 사회적 평판을 높인다. $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$이 적절하므로 결혼식에 한 번 더 참석할 수 있다.

이 예에서는 두 번째 방법이 평판을 가장 높인다. $k$의 합이 $1 + 1 = 2$로 가능한 최댓값이기 때문이다.

반대로 첫 번째 지폐가 12라면, 위의 세 장을 내는 방법은 그 뒤로 참석을 막는다. 그러나 이때 $k$의 합은 3이므로 이 방법이 평판을 가장 높인다.

축의금으로 얻을 수 있는 $k$ 합의 최댓값을 구하라. 적절한 축의금을 낼 수 있는 한 결혼식에 얼마든지 참석할 수 있다고 가정한다.

첫 줄에 세 정수 $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$($0 \le a_i \le 10^8$)이 주어진다. $a_i$는 위에서 $i$번째 지폐의 값이다.

$k$ 합의 최댓값을 한 줄에 출력한다.