JOI-kun và các bạn sẽ chơi pháo que. Có tổng cộng \(N\) người. Sau khi được châm, một que pháo cháy đúng \(T\) giây.

Ban đầu, mọi người đứng dọc theo một con đường thẳng chạy theo hướng đông-tây. Họ được đánh số từ \(1\) đến \(N\). Với mọi \(i<j\), người thứ \(i\) đứng về phía tây của người thứ \(j\), hoặc hai người đứng cùng một vị trí. Khoảng cách từ người thứ \(i\) đến người ở xa nhất về phía tây, tức người thứ nhất, là \(X_i\) mét. JOI-kun là người thứ \(K\).

Chiếc bật lửa chỉ còn đủ nhiên liệu để châm một que pháo, nên trước tiên họ châm que pháo của JOI-kun. Sau đó, các que khác chỉ có thể được châm bằng cách chạm vào một que đang cháy. Mỗi lần truyền lửa phải thỏa mãn:

• Việc chạm phải diễn ra không quá \(T\) giây kể từ khi que đang cháy được châm; thời điểm đúng \(T\) giây vẫn được phép.
• Que sắp được châm chưa từng cháy trước đó.
• Hai người liên quan phải ở cùng một vị trí.

Thời gian cần để truyền lửa được xem là bằng \(0\).

Mọi người có thể chạy về phía đông hoặc phía tây với tốc độ tùy ý, nhưng để bảo đảm an toàn, tốc độ của mỗi người không được vượt quá \(s\) mét mỗi giây, trong đó \(s\) là một số nguyên không âm.

Yêu cầu

Tính số nguyên nhỏ nhất \(s\) sao cho có thể châm được tất cả các que pháo.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên \(N,K,T\): số người, chỉ số của JOI-kun và thời gian một que pháo duy trì ngọn lửa.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(X_i\), là khoảng cách ban đầu từ người thứ \(i\) đến người thứ nhất.

Dữ liệu ra

In ra số nguyên nhỏ nhất \(s\) sao cho có thể châm tất cả các que pháo nếu giới hạn tốc độ là \(s\) mét mỗi giây.

Ràng buộc

• \(1 \le K \le N \le 100\,000\).
• \(1 \le T \le 1\,000\,000\,000\).
• \(0 \le X_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(X_1=0\).
• \(X_i \le X_j\) với mọi \(1 \le i \le j \le N\).

Phân nhóm

1. Subtask 1 (30 điểm): \(N \le 20\).
2. Subtask 2 (20 điểm): \(N \le 1\,000\).
3. Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.

Ví dụ

3 2 50
0
200
300

2

3 2 10
0
200
300

8

20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192

6