0363 - ウォッチング (Watching)

問題

　オーストラリアには，様々なスポーツや様々な動物など，興味深い文化がたくさんある．あなたは，ブリスベンのある道路で行われるイベントのウォッチングをしようと考えた．
　道路は東西に 1 列に並んだ 1 000 000 000 個のマス目からなり，最も西のマスから順に 1, 2, ..., 1 000 000 000 の番号がついている．あなたがウォッチングしたいイベントは N 個あり，i 番目のイベントはマス A_i で行われる．
　イベントのウォッチングのために，小型カメラ P 台と大型カメラ Q 台が用意されている．撮影用パラメータとして，あなたは正の整数 w を指定することができる．1 台の小型カメラはある連続する最大 w マスを，1 台の大型カメラはある連続する最大 2w マスを撮影することができる．同じマスを複数のカメラが撮影してもよいが，イベントが行われるすべてのマスを撮影したい．また，イベントには多くの参加者が来場することが予想されるため，安全のためカメラの位置は固定するものとし，イベントの最中にカメラを動かすことはできない．パラメータ w が大きいほど撮影には費用がかかるので，あなたは w の値を最小にしたい．

課題

　イベントの情報およびカメラの台数が与えられたとき，イベントが行われるすべてのマスを撮影するための w の最小値を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には整数 N, P, Q が空白を区切りとして書かれており，それぞれイベントの個数，小型カメラの台数，大型カメラの台数を表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には整数 A_i が書かれており，i 番目のイベントがマス A_i で行われることを表す．

出力

　標準出力に，イベントが行われるすべてのマスを撮影するための w の最小値を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす.

• 1 ≤ N ≤ 2 000．
• 1 ≤ P ≤ 100 000．
• 1 ≤ Q ≤ 100 000．
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．

小課題

小課題 1 [50 点]

• N ≤ 100 を満たす．

小課題 2 [50 点]

　追加の制限はない．

入出力例

入力例 1

3 1 1
2
11
17

出力例 1

4

　この例では，w = 4 とするとイベントが行われるすべてのマスを撮影することができる．例えば，1 台の小型カメラでマス 1 からマス 3 まで，1 台の大型カメラでマス 11 からマス 18 までを撮影すればよい．

入力例 2

13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75

出力例 2

9