Bali Sculptures Batch 컴파일 명령

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

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

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

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

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

• P와 Q를 2진수로 변환.
• nP를 P의 비트 수라고 하고, nQ를 Q의 비트 수라고 하자. M은 max(nP, nQ)이다.
• P의 이진수 표현이 p_M - 1p_M2... p₁p₀이고 Q의 이진수 표현이 q_M - 1q_M2... q₁q₀라고 하자. 단, p_i와 q_i는 각각 P와 Q의 i번째 비트이다. 첨자가 (M - 1)인 비트가 가장 높은 자리수이며 첨자가 0인 비트가 가장 낮은 자리수이다.
• 2진수로 P OR Q의 결과는 (p_M - 1 OR q_M - 1)(p_M - 2 OR q_M - 2)... (p₁ OR q₁)(p₀ OR q₀)이다. 단,
  • 0 OR 0 = 0
  • 0 OR 1 = 1
  • 1 OR 0 = 1
  • 1 OR 1 = 1

입력 양식

첫 줄에는 세 개의 정수 N, A, B가 주어진다. 둘째 줄에는 N개의 정수 Y₁, Y₂, ..., Y_N이 주어진다.

출력 양식

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

설명

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

부분문제

부분 문제 1 (9점)

• 1 ≤ N ≤ 20
• 1 ≤ A ≤ B ≤ N
• 0 ≤ Y_i ≤ 1, 000, 000, 000

부분 문제 2 (16점)

• 1 ≤ N ≤ 50
• 1 ≤ A ≤ B ≤ min(20, N)
• 0 ≤ Y_i ≤ 10

부분 문제 3 (21점)

• 1 ≤ N ≤ 100
• A = 1
• 1 ≤ B ≤ N
• 0 ≤ Y_i ≤ 20

부분 문제 4 (25점)

• 1 ≤ N ≤ 100
• 1 ≤ A ≤ B ≤ N
• 0 ≤ Y_i ≤ 1, 000, 000, 000

부분 문제 5 (29점)

• 1 ≤ N ≤ 2, 000
• A = 1
• 1 ≤ B ≤ N
• 0 ≤ Y_i ≤ 1, 000, 000, 000