Có ~n~ thành phố, thành phố thứ ~i~ có ~a_i~ nhà máy điện. Một nhà máy ở thành phố ~i~ cung cấp điện cho các thành phố cách ~i~ không quá ~r~. Được xây thêm tối đa ~k~ nhà máy ở bất kỳ thành phố nào, hãy tối đa hóa sức mạnh nhỏ nhất của mọi thành phố.

Dữ liệu vào

Dòng đầu chứa ~n~, ~r~ và ~k~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Dữ liệu ra

In giá trị lớn nhất có thể của sức mạnh nhỏ nhất.

Giới hạn

~1 \le n \le 100000~, ~0 \le r < n~, ~0 \le k \le 10^{18}~, ~0 \le a_i \le 10^{9}~.

V? d?

Input

1 0 10
0

Output

10