B. Board Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Students of Innopolis have come up with a new board game. The game is cooperative, meaning that players must work together to achieve a specific goal. One of the phases of the game involves distributing resources.

The game is designed for exactly $$$n$$$ players, and during the resource distribution phase $$$n$$$ cards with integers, ordered in non-decreasing order, are distributed among the players in order. Let $$$a_i$$$ be the number received by the $$$i$$$-th player (then $$$a_i \le a_{i+1}$$$ for all $$$i \le n - 1$$$). We call the set of three numbers $$$\{a_{i-1}, a_i, a_{i+1}\}$$$, i.e., the number written on his card and the two numbers of his neighbors, the options of the $$$i$$$-th player. The players sit in a circle, so for the first player instead of $$$a_{i-1}$$$ the first option will be $$$a_n$$$, and for the $$$n$$$-th player instead of $$$a_{i+1}$$$ the third option will be $$$a_1$$$.

Each player must choose exactly one of the available options and receive exactly that many resources from the bank. Then, the bitwise "AND" operation (the '&' operation) is performed on the two remaining options and the resulting number of points is added to the players' score for this round. For example, if a player has the options $$$\{2, 5, 11\}$$$ and chooses to take $$$5$$$ resources, he gets $$$2\ \&\ 11 = 0010_2\ \&\ 1011_2 = 2$$$ points. To successfully move on to the next phase of the game:

  1. the total amount of resources taken by the players must not exceed $$$\left(\sum\limits_{i=1}^n a_i\right) + X$$$, i.e., it must not exceed the amount of resources in the case where each player chooses his own $$$a_i$$$ by more than $$$X$$$;
  2. the total number of points earned must be maximized.

Help the players make their choices and successfully move on to the next phase. Note that it is not necessary to maximize the amount of resources taken within this upper limit; only the number of points needs to be maximized.

Input

The first line of input contains two space-separated integers $$$n$$$ and $$$X$$$ — the number of players and the limit on the "extra" number of resources ($$$3 \le n \le 300$$$; $$$0 \le X \le 10^5$$$).

The second line contains $$$n$$$ space-separated integers $$$a_i$$$ — the values written on the cards given to the players ($$$0 \le a_i \le 10^5$$$; $$$a_i \le a_{i+1}$$$).

Output

Output a single integer — the maximum number of points that the players can earn in this phase.

Scoring

Points for each subtask are awarded only if all tests for that subtask and any necessary subtasks are successfully passed.

SubtaskPointsConstraints Necessary subtasks Feedback policy
0–examplesfull
113$$$n \le 14$$$0full
28$$$1 \le a_i \le 2$$$ for all $$$i$$$first error
310$$$a_i \le 3$$$ for all $$$i$$$2first error
412$$$a_n - a_1 \le 1$$$2first error
517$$$a_i\ \&\ a_{i+1} = a_i$$$ for all $$$i$$$first error
616$$$a_i \le 200$$$ for all $$$i$$$0, 2, 3first error
724no additional constraints0 – 6first error
Examples
Input
4 0
1 2 4 8
Output
0
Input
4 0
3 6 12 24
Output
22
Input
7 3
1 2 3 4 5 6 7
Output
26
Note

In the first example $$$a_i\ \&\ a_j = 0$$$ for $$$i \ne j$$$, so it is not possible to score any points.

In the second example the players should take resources in quantities of $$$24$$$, $$$3$$$, $$$6$$$, and $$$3$$$ respectively. Then the number of points is equal to $$$(3\ \&\ 6) + (6\ \&\ 12) + (12\ \&\ 24) + (12\ \&\ 24) = 2 + 4 + 8 + 8 = 22$$$.