Franklin đang chơi một trò chơi điện tử hành động theo thời gian mới nhất và phải đối mặt với một thử thách "boss rush": một chuỗi các trận chiến cam go nơi cậu phải đánh bại $N$ quái vật (các con trùm) để sống sót. Khả năng duy nhất của cậu, đỡ đòn (parry), cực kỳ mạnh mẽ nhưng rất khó sử dụng.

Mỗi con trùm tấn công Franklin một lần sau mỗi $d$ giây; tuy nhiên, các con trùm có độ trễ bắt đầu riêng trước khi chúng bắt đầu chuỗi tấn công của mình, vì vậy các đòn tấn công của chúng được phân bổ so le. Cụ thể hơn, nếu $f_i$ là độ trễ bắt đầu của con trùm thứ $i$, thì con trùm đó sẽ tấn công vào các giây $f_i, f_i + d, f_i + 2d, \dots$

Để tự vệ, Franklin có thể đỡ một đòn tấn công vào đúng giây nó xảy ra, ngay lập tức đánh bại con trùm đó và kết thúc tất cả các đòn tấn công sau đó của nó. Franklin chỉ có thể đỡ một đòn tấn công tại một thời điểm: nếu nhiều con trùm tấn công cậu cùng lúc, cậu có thể đỡ tối đa một trong số những đòn tấn công đó.

Hơn nữa, sau khi đỡ một đòn tấn công, Franklin bị hụt hơi và không thể đỡ đòn lần nữa trong vòng $w$ giây tiếp theo. Theo hình thức, nếu Franklin đỡ một đòn tấn công vào giây $t$, thời điểm sớm nhất mà Franklin có thể đỡ một đòn tấn công khác là giây $t + w$.

Franklin có rất nhiều máu và không quan tâm đến các đòn tấn công của lũ trùm nhắm vào mình, nhưng cậu muốn kết thúc trận chiến càng nhanh càng tốt. Hãy tính khoảng thời gian tối thiểu để Franklin đánh bại tất cả $N$ con trùm nếu cậu đỡ đòn một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên cách nhau bởi dấu cách $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$), và $d$ ($1 \le d \le 10^9$), trong đó $N$ là số lượng trùm, $w$ là số giây Franklin phải chờ sau khi đỡ đòn trước khi có thể đỡ đòn tiếp theo, và $d$ là số giây giữa hai đòn tấn công của cùng một con trùm.

Dòng tiếp theo chứa $N$ số nguyên cách nhau bởi dấu cách $f_i$ ($0 \le f_i < d$), là độ trễ bắt đầu của mỗi con trùm tính bằng giây.

Dữ liệu ra

In ra số giây cần thiết để Franklin đánh bại tất cả $N$ con trùm nếu cậu đỡ đòn một cách tối ưu.

Ghi chú

Giải thích cho Ví dụ 1: Con trùm đầu tiên tấn công Franklin vào giây 2; Franklin có thể đỡ đòn nhưng chọn chờ đợi và thay vào đó đỡ đòn tấn công của con trùm thứ hai vào giây 3. Cậu bị hụt hơi và không thể đỡ đòn lần nữa trước giây 7.

Con trùm thứ ba tấn công Franklin vào giây 8 và Franklin đỡ đòn đó. Cậu lại bị hụt hơi và không thể đỡ đòn cho đến giây 12: vừa kịp lúc để đỡ đòn tấn công thứ hai của con trùm đầu tiên, kết thúc trận chiến.

Ví dụ

Ví dụ 1

3 4 10
2 3 8

Ví dụ 1

12

Ví dụ 2

3 4 10
2 3 9

Ví dụ 2

13