시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 40 20 20 57.143%

문제

발리의 길에는 많은 조각상들이 있다. 큰길 하나에 있는 조각상들을 생각해 보자.

그 길에는 N개의 조각상들이 있고 1부터 N까지 순서대로 번호가 붙어 있다. 조각상 i의 나이는 Yi년이다, 즉, Yi년 전에 만든 것이다. 길을 더 아름답게 만들기 위해 정부는 조각상들을 몇 개의 그룹으로 나누려고 한다. 그룹이 정해지고 나면 그룹들 사이에 아름다운 나무들을 심어서 관광객이 더 많이 오도록 만들려는 것이다.

조각상을 그룹으로 분할하는 규칙은 다음과 같다.

  • 조각상들은 정확히 X개의 그룹으로 분할되어야 한다. 단, AXB이다. 각 그룹에는 최소한 하나의 조각상이 있어야 한다. 각 조각상은 단 하나의 그룹에만 속해야 한다. 각 그룹의 조각상들은 도로 상에 연속으로 존재해야 한다.
  • 각 그룹에 대해서, 그룹에 속한 조각상들의 나이를 더한다.
  • 그룹 별 합에 대해서, 모든 그룹 별 합의 비트 OR를 계산한다. 이 값을 분할의 아름다움 정도라고 하자.
  • 아름다움 정도를 최소화 한다면 어떤 값이 될 것인가?

주의; 음수가 아닌 두 정수 PQ의 비트 OR는 다음과 같이 계산한다:

  • PQ를 2진수로 변환.
  • nPP의 비트 수라고 하고, nQQ의 비트 수라고 하자. M은 max(nP, nQ)이다.
  • P의 이진수 표현이 pM - 1pM2... p1p0이고 Q의 이진수 표현이 qM - 1qM2... q1q0라고 하자. 단, piqi는 각각 PQi번째 비트이다. 첨자가 (M - 1)인 비트가 가장 높은 자리수이며 첨자가 0인 비트가 가장 낮은 자리수이다.
  • 2진수로 P OR Q의 결과는 (pM - 1 OR qM - 1)(pM - 2 OR qM - 2)... (p1 OR q1)(p0 OR q0)이다. 단,
    • 0 OR 0 = 0
    • 0 OR 1 = 1
    • 1 OR 0 = 1
    • 1 OR 1 = 1

입력

첫 줄에는 세 개의 정수 N, A, B가 주어진다. 둘째 줄에는 N개의 정수 Y1, Y2, ..., YN이 주어진다.

  • 1 ≤ N ≤ 2,000
  • 1 ≤ A ≤ B ≤ N
  • 0 ≤ Yi ≤ 1, 000, 000, 000
  • N이 100을 초과하는 경우, A = 1임이 보장된다.

출력

출력은 단 한 줄이며 최소로 가능한 아름다움 정도를 출력해야 한다.

예제 입력

6 1 3
8 1 2 1 5 4

예제 출력

11

힌트

조각상들을 다음의 나이가 되도록 두 그룹으로 나눈다: (8 1 2) and (1 5 4). 그룹 별 합은 11과 10이다. 비트 OR을 계산하면 11이 된다.