Franklin은 최신 유행하는 시간 제한 액션 비디오 게임을 플레이하고 있으며, 보스 러시(boss rush)에 직면해 있습니다. 이는 그가 살아남기 위해 $N$명의 몬스터(보스)를 물리쳐야 하는 힘겨운 관문입니다. 그의 유일한 능력인 패리(parry)는 매우 강력하지만 사용하기가 매우 어렵습니다.

각 보스는 $d$초마다 한 번씩 Franklin을 공격합니다. 하지만 보스마다 공격을 시작하기 전 고유한 시작 지연 시간이 있어 보스의 공격은 서로 엇갈리게 됩니다. 더 구체적으로, $i$번째 보스의 시작 지연 시간이 $f_i$라면, 해당 보스는 $f_i, f_i + d, f_i + 2d, \dots$ 초에 공격합니다.

자신을 방어하기 위해 Franklin은 공격이 일어나는 정확한 초에 패리를 사용하여 보스를 즉시 물리치고 그 이후의 모든 공격을 끝낼 수 있습니다. Franklin은 한 번에 하나의 공격만 패리할 수 있습니다. 만약 여러 보스가 동시에 공격한다면, 그중 최대 하나의 공격만 패리할 수 있습니다.

게다가 공격을 패리한 후 Franklin은 숨이 차서 다음 $w$초 동안은 다시 패리할 수 없습니다. 형식적으로, Franklin이 $t$초에 공격을 패리했다면, 그가 다음 공격을 패리할 수 있는 가장 빠른 시점은 $t + w$초입니다.

Franklin은 체력이 충분하여 보스의 공격에 대해 걱정하지 않지만, 가능한 한 빨리 싸움을 끝내고 싶어 합니다. Franklin이 최적으로 패리할 때 모든 $N$명의 보스를 물리치는 데 걸리는 최소 시간을 계산하세요.

입력

첫 번째 줄에는 세 개의 정수 $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$), $d$ ($1 \le d \le 10^9$)가 공백으로 구분되어 주어집니다. 여기서 $N$은 보스의 수, $w$는 Franklin이 패리 후 다시 패리하기 전까지 기다려야 하는 시간(초), $d$는 같은 보스가 공격하는 간격(초)입니다.

다음 줄에는 각 보스의 시작 지연 시간(초)을 나타내는 $N$개의 정수 $f_i$ ($0 \le f_i < d$)가 공백으로 구분되어 주어집니다.

출력

Franklin이 최적으로 패리할 때 모든 $N$명의 보스를 물리치는 데 걸리는 시간을 초 단위로 출력하세요.

예제

입력 1

3 4 10
2 3 8

출력 1

12

참고 1

첫 번째 보스는 2초에 Franklin을 공격합니다. Franklin은 이 공격을 패리할 수 있지만, 시간을 기다렸다가 3초에 두 번째 보스의 공격을 패리하기로 선택합니다. 그는 이제 숨이 차서 7초 전까지는 다시 패리할 수 없습니다.

세 번째 보스는 8초에 공격하며 Franklin은 이 공격을 패리합니다. 그는 다시 숨이 차서 12초까지 패리할 수 없게 되는데, 이는 첫 번째 보스의 두 번째 공격을 패리하기에 딱 맞는 시간이며, 이로써 싸움이 끝납니다.

입력 2

3 4 10
2 3 9

출력 2

13