Another Random Contest 1 P3 - Physics Olympics

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

Andy is on his school's team for the UBC Physics Olympics. During the competition, however, he remembered that he only had a 60% in Physics class and didn't know how to solve any of the problems. Since he has K other teammates, he is just going to AFK and let them do all the work for him.

There are N problems in the contest. Andy realized that some of his teammates would deceive the rest of his team about the solution to each problem. Andy calculated how much each teammate would deceive the team for each problem, X_{i, j}, where i is the student number, and j is the problem number. For each teammate, he can strategically annoy them on one problem to set their deception value to 0 (note that he can choose not to annoy any teammate). For each problem, Andy can only annoy one teammate.

The deception value for a problem is the XOR sum of all the deception values of all his teammates. The total deception value for the contest is the sum of all the individual values of each problem.

Andy wishes to know the minimum overall deception value possible, so determine it for him.


For all test cases:

1\le N \le 2 \times 10^4

1 \le K \le 11

0 \le X_{i, j} \le 10^4

Input Specification

The first line contains two integers N and K, the number of tasks and teammates.

The next K lines each contain N integers, with each row representing a student and each number in the row representing the deception value of that student in that problem.

Output Specification

Output the minimum deception value of the contest.

Sample Input

5 3
3 3 0 3 5
5 5 4 3 5
1 5 4 2 1

Sample Output


Sample Explanation

A way to minimize the deception value is to annoy teammate 2 on the first problem, teammate 1 on the second problem, and teammate 3 on the fourth problem.

This results in a deception level of {2, 0, 0, 0, 1} for the problems, meaning the total deception value is 2 + 0 + 0 + 0 + 1 = 3.


There are no comments at the moment.