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, các ô còn lại đã được sơn.

Một cây cọ có kích thước ~w~ có thể sơn ~w~ ô liên tiếp. Cụ thể, nếu chọn ~x~ là vị trí bắt đầu thì cây cọ sẽ sơn toàn bộ các ô từ ~x~ đến ~x + w - 1~. Cây cọ được phép quét ra ngoài dải ô, điều đó không ảnh hưởng tới bài toán.

Bạn dự định mua:

• ~a~ cây cọ kích thước ~w~,
• ~b~ cây cọ kích thước ~2w~.

Mỗi cây cọ được dùng nhiều nhất một lần. Một ô có thể bị sơn nhiều lần.

Do cọ càng lớn thì càng đắt, hãy tìm giá trị ~w~ nhỏ nhất sao cho có thể sơn hết tất cả các ô chưa được sơn.

Yêu cầu

Tìm giá trị nguyên dương nhỏ nhất của ~w~ để sơn được hết các ô chưa được sơn.

Dữ liệu

• Dòng đầu chứa ba số nguyên ~n, a, b~.
• Dòng thứ hai chứa ~n~ số nguyên phân biệt ~x_1, x_2, \ldots, x_n~, là vị trí của các ô chưa được sơn.

Kết quả

In ra một số nguyên duy nhất là giá trị nhỏ nhất của ~w~.

Ví dụ

Ví dụ 1

Input

5 1 1
1 2 3 4 5

Output

2

Ví dụ 2

Input

7 3 0
1 3 4 5 7 9 10

Output

4

Giải thích

Ví dụ 1

Chọn ~w = 2~.

• Cây cọ kích thước ~2~ sơn các ô từ vị trí ~1~ đến ~2~.
• Cây cọ kích thước ~4~ sơn các ô từ vị trí ~2~ đến ~5~.

Như vậy mọi ô chưa được sơn đều được phủ.

Ví dụ 2

Với ~w = 4~, có ~3~ cây cọ kích thước ~4~ và không có cây cọ kích thước ~8~. Ta có thể sơn phủ toàn bộ các ô chưa được sơn. Không tồn tại giá trị ~w~ nhỏ hơn thỏa mãn yêu cầu.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2000~.
• ~0 \le a, b \le 10^9~.
• ~1 \le a + b~.
• ~1 \le x_i \le 10^9~.
• Các giá trị ~x_i~ đôi một phân biệt.

Chấm điểm

• 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.