Sắp xếp đá quý

Trong vương quốc Lumina, có một cuộc thi sắp xếp đá quý hàng năm. Một dải ô dài vô hạn được sử dụng cho cuộc thi. Ban giám khảo đã đặt \(n\) viên đá quý chưa được đánh bóng tại các vị trí \(x_1, x_2, \ldots, x_n\). Các vị trí còn lại đã có đá quý lấp lánh.

Một "máy đánh bóng" được dùng để làm lấp lánh các viên đá quý. Máy có thể hoạt động với hai chế độ:

• Chế độ 1: Máy đánh bóng \(w\) viên đá liên tiếp.
• Chế độ 2: Máy đánh bóng \(2 \times w\) viên đá liên tiếp

Để sử dụng máy, bạn phải chọn một vị trí bắt đầu \(x\) và chế độ hoạt động. Máy sẽ đánh bóng tất cả các viên đá từ vị trí \(x\) đến \(x + \text{kích thước w} - 1\). Một viên đá có thể được đánh bóng nhiều lần.

Mục tiêu của bạn là làm lấp lánh tất cả \(n\) viên đá quý chưa được đánh bóng. Bạn đã chuẩn bị \(a\) lượt sử dụng máy ở chế độ 1 và \(b\) lượt sử dụng ở chế độ 2. Để tiết kiệm năng lượng, bạn muốn tìm giá trị \(w\) nhỏ nhất có thể.

Yêu cầu: Hãy tìm giá trị \(w\) nhỏ nhất để có thể đánh bóng tất cả các viên đá quý chưa được đánh bóng.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, a\) và \(b\) (\(1 \le n \le 2000, 0 \le a, b \le 10^9, a + b \ge 1\)).
• Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(x_1, x_2, \ldots, x_n\) (\(1 \le x_i \le 10^9\)) là vị trí của những viên đá quý chưa được đánh bóng.

Output

• Một số nguyên duy nhất là giá trị \(w\) nhỏ nhất tìm được.

Example

5 1 1
1 2 3 4 5

2

7 3 0
1 3 4 5 7 9 10

4

Scoring

• Subtask 1 (20% số điểm): Các ô chưa được sơn đứng cạnh nhau.
• Subtask 2 (20% số điểm): \(b = 0\).
• Subtask 3 (30% số điểm): \(n \le 200\).
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.