Quan sát

Cho một con đường được chia thành \(10^9\) đoạn, đánh số từ \(1\) đến \(10^9\) theo hướng tây → đông.

Có \(N\) sự kiện diễn ra trên đường. Sự kiện thứ \(i\) diễn ra tại đoạn \(A_i\).

Bạn có \(P\) camera nhỏ và \(Q\) camera lớn. Bạn được chọn một số nguyên dương \(w\) làm tham số chụp ảnh:

• Mỗi camera nhỏ chụp được nhiều nhất \(w\) đoạn liên tiếp.
• Mỗi camera lớn chụp được nhiều nhất \(2w\) đoạn liên tiếp.

Một đoạn có thể được chụp bởi nhiều camera khác nhau. Mục tiêu là chụp được tất cả các đoạn mà có sự kiện diễn ra. Camera không được di chuyển sau khi đặt.

Hãy tìm giá trị nhỏ nhất của \(w\) sao cho có thể chụp toàn bộ các sự kiện bằng cách đặt tối đa \(P\) camera nhỏ và \(Q\) camera lớn.

Input

• Dòng đầu chứa ba số nguyên \(N, P, Q\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(A_i\).

Output

In ra giá trị nhỏ nhất của \(w\).

Constraints

• \(1 \le N \le 2000\).
• \(1 \le P, Q \le 10^5\).
• \(1 \le A_i \le 10^9\).

Subtasks

• Subtask 1 (50 points): \(N \le 100\).
• Subtask 2 (50 points): Không có ràng buộc thêm.

Example

3 1 1
2
11
17

4