課題(Description)
バリ州の道路沿いには多くの彫像がある．ここでは，ある 1 本の幹線道路に注目する．
この幹線道路沿いには N 個の彫像があり，並んでいる順に 1 から N までの番号が付けられている．彫像 i は制作後 Yi 年が経過している．道路をより美しくするため，政府は彫像をいくつかのグループに分けることにした．政府はグループとグループの間に美しい木を植えることによって，より多くのバリ州への観 光客の注目を集めようと考えている．
彫像のグループ分けは，以下のルールで行う.
- グループの個数 X は，A ≤ X ≤ B を満たさなければならない．いずれのグループにも 1 個以上の彫像が属していなければならず，いずれの彫像もちょうど 1 個のグループに属していなければならない．また，各グループに属している彫像は，道路上の連続した彫像でなければならない．
- 各グループについて，そのグループに属している彫像の制作後経過年数の和を計算する．
- 最後に，上で計算した和のビットごとの OR の値を計算する．この値をグループ分けの最終的な美的価値 (final beauty value) と呼ぶ．
政府が達成しうる最終的な美的価値の最小値はいくらだろうか．
注意(Note)
0 以上の整数 P, Q のビットごとの OR は次のように計算される．
- まず，P, Q を二進法表記に変換する．
- nP を P を二進法で書いたときの桁数，nQ を Q を二進法で書いたときの桁数とし， M = max(nP, nQ) とする．
- P を二進法で pM-1pM-2 .. p1p0 と表し，Q を二進法で qM-1qM-2 .. q1q0 と表す．ここで pi, qi はそれぞれ，P, Q の i ビット目である．M − 1 ビット目は最上位ビットであり，0 ビット目は最下位ビットである．
- P, Q のビットごとの OR とは，二進法で (pM-1 OR qM-1)(pM-2 OR qM-2)..(p1 OR q1)(p0 OR q0) と表される数のことである．ただし，OR は以下の演算である．
- 0 OR 0 = 0
- 0 OR 1 = 1
- 1 OR 0 = 1
- 1 OR 1 = 1
入力形式(Input Format)
1 行目には，3 個の整数 N, A, B が空白を区切りとして書かれている．
2 行目には，N 個の整数 Y1, Y2, ..., YN が空白を区切りとして書かれている．
出力形式(Ouput Format)
最終的な美的価値の最小値を 1 行で出力せよ．
入力例(Sample Input)
6 1 3 8 1 2 1 5 4
出力例(Sample Output)
11
解説(Explanation)
彫像を (8 1 2), (1 5 4) の 2 個のグループに分ける．グループに属している彫像の制作後経過年数の和は，それぞれ 11, 10 である．最終的な美的価値は，11, 10 のビットごとの OR である 11 となる．
小課題(Subtasks)
小課題 1 (Subtask 1) [9 点]
- 1 ≤ N ≤ 20
- 1 ≤ A ≤ B ≤ N
- 0 ≤ Yi ≦ 1,000,000,000
小課題 2 (Subtask 2) [16 点]
- 1 ≤ N ≤ 50
- 1 ≤ A ≤ B ≤ min(20, N)
- 0 ≤ Yi ≤ 10
小課題 3 (Subtask 3) [21 点]
- 1 ≤ N ≤ 100
- A = 1
- 1 ≤ B ≤ N
- 0 ≤ Yi ≤ 20
小課題 4 (Subtask 4) [25 点]
- 1 ≤ N ≤ 100
- 1 ≤ A ≤ B ≤ N
- 0 ≤ Yi ≤ 1,000,000,000
小課題 5 (Subtask 5) [29 点]
- 1 ≤ N ≤ 2,000
- A = 1
- 1 ≤ B ≤ N
- 0 ≤ Yi ≤ 1,000,000,000