Cho một dải ô gồm \(10^9\) ô vuông liên tiếp, trong đó có \(n\) ô chưa được sơn màu và những ô còn lại đã được sơn. Một cây cọ sơn kích thước \(w\) có thể quét sơn cho \(w\) ô liên tiếp, cụ thể là nếu chọn \(x\) (\(1 \leq x \leq 10^9\)) là vị trí bắt đầu thì cây cọ có thể quét sơn toàn bộ các ô liên tiếp từ vị trí \(x\) đến \(x + w - 1\) (có thể quét ra ngoài, không ảnh hưởng đến bài toán).

Bạn đang lên kế hoạch để sơn hết các ô chưa được sơn. Bạn dự định mua \(a\) cây cọ sơn kích thước \(w\) và \(b\) cây cọ sơn kích thước \(2 \times w\), mỗi cây cọ sẽ được dùng để sơn nhiều nhất một lần và mỗi ô có thể được sơn nhiều lần. Nhưng cây cọ có kích thước càng lớn thì giá cả lại càng cao, vì vậy bạn muốn tìm giá trị \(w\) nhỏ nhất có thể. Hãy tìm giá trị \(w\) đó.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(a\) và \(b\) \((1 \leq n \leq 2000, 0 \leq a, b \leq 10^9, a + b \geq 1)\) lần lượt là số ô chưa được tô màu, số cây cọ sơn kích thước \(w\) và \(2 \times w\).
• Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(x_1, x_2, \ldots, x_n\) \((1 \leq x_i \leq 10^9)\) là vị trí của những ô chưa được sơn.

Output

• Một số nguyên duy nhất là giá trị \(w\) nhỏ nhất để có thể sơn hết những ô chưa được sơn.

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 \leq 200\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 1 1
1 2 3 4 5

2

7 3 0
1 3 4 5 7 9 10

4