Maximizing Team Success Rate

You are given a total of n people and k abilities (indexed from 1 to k). Each person has some of these abilities. A team can be formed by selecting a subset of these people. For each ability, if an odd number of team members possess this ability, then the team has that ability. Otherwise, if an even number of members (including zero) possess the ability, the team loses that ability.

Each ability contributes a score (weight) to the overall success rate of your plan. The weight for the first ability is \(2^{k-1}\), the second ability \(2^{k-2}\), and so on, with the \(k\)-th ability having a weight of \(1\). The overall score is the sum of weights for all abilities the team possesses.

Your task is to select a subset of people so that the total score (i.e. the sum of the weights corresponding to abilities for which an odd number of selected people have that ability) is maximized. Note that the parity for each ability is equivalent to the bitwise XOR on the corresponding bits from each person. Thus, if we represent each person with a binary string of length k, the problem reduces to finding a subset whose XOR (when interpreted as a binary number) is as high as possible.

Input and output formats are described below.

inputFormat

The input begins with a line containing two integers n and k (\(1 \le n \le 10^5\), \(1 \le k \le 50\)), representing the number of people and the number of abilities, respectively.

Each of the following n lines contains a binary string of length k. The \(j\)-th character in the string is '1' if the person has the \(j\)-th ability and '0' otherwise.

outputFormat

Output a single integer which is the maximum possible success rate score, i.e. the maximum sum of weights corresponding to abilities that the team possesses under the optimal selection.

The score is calculated by interpreting the bitwise XOR of the selected persons' ability vectors as a binary number. In other words, if the XOR result is the binary number \(b_1b_2...b_k\), the score is \(\sum_{i=1}^{k} b_i \times 2^{k-i}\).

sample

3 3
101
010
111

7