Or Problem

Time limit: 5000 ms
Memory limit: 256 MB

You are given an array AA of NN integers. The cost of a subarray is defined as the bitwise or value of all its elements. Suppose you split the array into KK non-empty subarrays and you compute the sum of their costs. What is the maximum value you can get?

Standard input

The first line contains two integers NN and KK.

The second line contains NN integers representing array AA.

Standard output

The first line will contain the maximal possible answer.

Constraints and notes

  • 1KN21051 \leq K \leq N \leq 2 * 10^5
  • 0Ai<2200 \leq A_i < 2^{20}

InputOutputExplanation
5 2
1 4 3 4 8
20

Put the first 22 elements in one subarray and the remaining 33 in the other.

The answer will be (A1OR A2)+(A3 OR A4 OR A5)=5+15=20(A_1 \text{OR}\ A_2) + (A_3 \ \text{OR}\ A_4 \ \text{OR}\ A_5) = 5 + 15 = 20.

Authenticate to use the workspace

Log In
Sign Up
Forgot Password?
or connect with