시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 44 15 8 44.444%

문제

크기가 N인 수열 A와 정수 K가 주어진다. 이 때, 수열을 K개의 연속된 비어있지 않은 그룹으로 나누어야 한다. 수열의 모든 원소는 한 그룹에 포함되어 있어야 한다.

각각의 그룹은 두 정수 L과 R로 나타낼 수 있으며, L번째 수부터 R번째 수까지 그룹에 포함된다는 의미를 가진다. 그룹의 비용은 그룹에 속한 모든 원소를 비트 연산 OR한 값이다.

수열의 OR 점수는 모든 그룹의 점수를 합한 것이다.

수열을 K개의 연속된 비어있지 않은 그룹으로 나누어서 수열의 OR 점수의 최대값을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 N (1 ≤ N ≤ 5000)과 K (1 ≤ K ≤ N)이 주어진다.

둘재 줄에는 수열의 원소 Ai (0 ≤ Ai ≤ 230)이 주어진다.

출력

수열의 OR 점수의 최대값을 출력한다.

예제 입력

3 2
1 2 2

예제 출력

5

예제 입력 2

4 3
1 2 3 4

예제 출력 2

10

예제 입력 3

2 2
1 2

예제 출력 3

3

예제 입력 4

11 4
66 152 7 89 42 28 222 69 10 54 99

예제 출력 4

704

힌트

첫 번째 예제의 경우에 (1, 2), (2)로 나누면 (1 OR 2) + 2 = 3 + 2 = 5가 된다.

두 번째 예제의 경우에 (1, 2), (3), (4)로 나누면, (1 OR 2) + 3 + 4 = 3 + 3 + 4 = 10이 된다.

세 번째 예제의 경우에는 (1), (2)로 나눠야 한다.

출처