Bessie rất thích xem các chương trình được chiếu trên Mooloo. Bởi vì Bessie là một cô bò bận rộn, cô ấy đã lên lịch cho \(N\) \((1 \le N \le 10^5)\) ngày xem Mooloo của mình. Do Mooloo là một dịch vụ trả tiền định kì, Bessie cần tối thiểu hoá số tiền mà cô ấy cần phải trả.

Mooloo có một cách đăng kí dịch vụ rất thú vị: bạn cần tốn \(d + K\) \((1 \le K \le 10^9)\) đồng moonies để sử dụng dịch vụ trong \(d\) ngày liên tiếp, bạn hoàn toàn có thể đăng kí tại bất cứ thời điểm nào, và có thể đăng kí gói mới không giới hạn số lần nếu như gói dịch vụ hiện tại đã hết hạn. Hãy cho Bessie biết số tiền ít nhất cần dành ra nhé!

Input

• Dòng đầu tiên là hai số \(N\) và \(K\).
• Dòng thứ hai là \(N\) ngày \(d_i\) \((1 \le i \le N)\) mà Bessie sẽ xem Mooloo, thoả mãn: \(1 < d_1 < d_2 < ... < d_N \le 10^{14}\).

Output

• Số tiền mà Bessie cần trả.

Scoring

• Subtask \(1\): \(N \le 10\).
• Subtask \(2\): Không có ràng buộc gì thêm.

2 4
7 9

7

2 3
1 10

8