Sau cuộc thi Olympic, BTC quyết định gửi tặng áo phông cho tất cả những người thắng cuộc. Việc giao áo phông được thực hiện bởi nhân viên Bill của công ty chuyển hàng Courrier. Bill sẽ phải chuyển \(n\) cái áo phông theo một thứ tự cho trước. Nếu theo thứ tự đó một cái áo phông nào đó không thể chuyển được thì các áo phông tiếp theo vẫn tiếp tục được chuyển theo thứ tự. Bill bắt đầu ngày làm việc tại văn phòng công ty vào thời điểm 0. Tại mỗi điểm giao hàng, Bill chỉ đợi ở đó không quá \(k\) phút và trong khoảng thời gian đợi đó nếu khách hàng xuất hiện để nhận thì Bill sẽ đưa cho anh ta một cái áo. Thời gian để chuyển cái áo phông cho khách không kể thời gian đợi là \(t\) phút. Nếu trong k phút chờ đợi mà khách hàng không xuất hiện để nhận thì Bill sẽ đi tiếp đến điểm tiếp theo trong lịch trình.

Nếu khách hàng xuất hiện đúng vào thời điểm \(k\) phút sau khi Bill đến thì Bill vẫn kịp giao hàng. Ngày làm việc của Bill kết thúc khi Bill giao gói hàng cuối hoặc là sau khi đợi xong khách hàng cuối mà không giao được. Ông chủ của Bill tên là John muốn đánh giá công việc của Bill. John đo trước được thời gian đi từ văn phòng đến điểm giao đầu và thời gian từ một điểm giao hàng đến điểm giao tiếp theo. John cũng đã liên lạc trước với khách hàng và biết chính xác là từ thời điểm nào trở đi là khách hàng có mặt ở nhà để nhận hàng. John muốn biết thời điểm nào trong ngày là kết thúc công việc của Bill.

Dữ liệu

Dòng đầu tiên chứa 3 số nguyên \(n, k, t (1 ≤ n ≤ 50 000, 1 ≤ k, t ≤ 10^4)\).

Dòng thứ hai chứa \(n\) số nguyên \(z_0, z_1, . . . , z_{n−1}\), với \(z_0\) là thời gian Bill cần để đi từ văn phòng đến điểm giao đầu tiên, và zi là thời gian Bill cần để di chuyển từ điểm giao thứ \(i\) sang điểm giao thứ \(i + 1\). Tất cả \(z_i\) không vượt quá \(10^4\).

Dòng thứ ba chứa \(n\) số nguyên không âm \(s_1, s_2, . . . , s_n (0 ≤ s_i ≤ 10^9)\) với \(s_i\) là thời điểm mà từ đó khách hàng ở điểm thứ \(i\) sẵn sàng nhận áo phông. Bill bắt đầu ngày làm việc tại thời điểm \(0\).

Kết quả

Ghi ra một số duy nhất là thời gian ít nhất mà Bill có thể hoàn thành công việc.

Sample Input

3 3 1
1 5 4
1 11 7

Sample Output

15

Giải thích

Trong ví dụ này, Bill đến điểm giao đầu tiên tại thời điểm 1 và ngay lập tức giao hàng.Tại thời điểm 2, Bill di chuyển tiếp từ điểm giao 1 và đến điểm giao 2 tại thời điểm 7. Bill đợi ở đó 3 phút đến thời điểm 10 nhưng vẫn không giao được nên Bill tiếp tục di chuyển đến điểm giao 3 và đến nơi tại thời điểm 14. Cuối cùng Bill giao hàng ở đây và kết thúc tại thời điểm 15.