Franklin 正在玩一款最新的熱門限時動作遊戲，並面臨一場「頭目連戰」（boss rush）：這是一場艱難的挑戰，他必須擊敗 $N$ 個怪物（頭目）才能生存。他唯一的能力「招架」（parry）非常強大，但極難使用。

每個頭目每隔 $d$ 秒會攻擊 Franklin 一次；然而，每個頭目在開始攻擊序列前都有各自的起始延遲，因此頭目的攻擊是錯開的。更具體地說，如果 $f_i$ 是第 $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