Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
In the last couple of years, the duology of movies about the big boss of the XOR-mafia Okram Ćivas made their way to the hearts of the audience. The duology consisted, as the name suggests, of two movies named Okram and Ćivas. However, due to the unexpected popularity of the last two movies, the production decided to film the third and last part of the series - “Sdneirf”. In this movie, Okram Ćivas has abandoned mafia long ago and happily lives with his family now. In the middle of a sunny day he spent picknicking with his family, Okram receives a call to complete one last mission…
In the last adventure of our hero, similarly to the first movie (nostalgy is very important in these movies), Okram finds himself in a misterious matrix of dimensions \(N\times M\). Every cell of this matrix contains a single nonnegative integer. More precisely, the cell at the intersection of \(i\)-th row and \(j\)-th column contains he value \(a_{i, j}\). Overcoming his initial confusion, Okram realizes that there is only one way he can change the values in cells of this matrix. In a move, he can choose a nonnegative integer \(X\) and a sequence of \(N+M-1\) fields starting at the top left corner and ending at the bottom right corner, such that every two adjacent cells in the sequence share an a side. For every cell of this sequence, if the current value in this cell is \(Y\), Okram will replace it by \(Y\text{ xor} X\).
Since Okram is very well known for his mastery of the XOR operation, he has to solve the following problem: after an arbitrary number of moves, what it the minimal possible sum of all values in the matrix? If Okram determines the minimal sum, he might have a chance to escape this matrix and the world of criminal forever.
The first line of the standard input contains two nonnegative integers, the number of rows \(N\) and the number of columns \(M\).
Each of the next \(N\) lines contains \(M\) integers, such that the \(j\)-th number in the \((i+1)\)-th line corresponds to \(a_{i, j}\).
Your program should output a single number: the least possible sum if the numbers in the matrix after an arbitrary number of moves.
1 2
1 01The starting sum is \(1\). This is also the minimal sum since the sum after any number of moves must be positive.
2 3
2 7 5
5 7 20In the first move, Okram can choose \(X=7\) and the sequence of cells \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\). After that, he can perform \(3\) moves with \(X=5\) and sequences of cells \((1,1),\) \((2,1),\) \((2,2),\) \((2,3)\), then \((1,1),\) \((1,2),\) \((1,3),\) \((2,3)\) and finally \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\). ## Constraints - \(1 \leq N,M \leq 1.500\) - \(0\leq A_{ij}\leq 1.000.000.000\)
The test cases are split into five disjoint groups:
The XOR operator in is denoted by ‘xor’ in Pascal, and by ‘^’ in C++. This operation \(x\ \text{xor} \ y\) for nonnegative integers \(x,y\) is defined in the following way. First, we write the numbers \(x\) and \(y\) in the binary system. If the number of digits of the two numbers is not equal, we add leading zeros until both numbers have the same number of digits. Thus, we obtain two binary sequences, denoted by \(a_1, \ldots, a_k\) and \(b_1, \ldots b_k\). Then, for every position \(i\in \{1, \dots, k\}\) one defines \(c_i\) using the following rules: - If \(a_{i} = 0, b_{i} = 0\) then \(c_{i} = 0\) - If \(a_{i} = 0, b_{i} = 1\) then \(c_{i} = 1\) - If \(a_{i} = 1, b_{i} = 0\) then \(c_{i} = 1\) - If \(a_{i} = 1, b_{i} = 1\) then \(c_{i} = 0\)
The sequence of binary digits \(c_1, \ldots, c_k\) (possibly with leading zeros) represents the result \(x \ \text{xor} \ y\) in the binary form.
If you want to learn more about previous adventures of Okram Ćivas, take a loot at the third problem in B category on the regional competition last year (titled Okram) as well as the second problem in the A cactegory on the regional competition last year (titled Ćivas).