PUCMM333 - Dividing Xorland

no tags 

Xorland is a beautiful Kingdom located in the northern part of the Hispaniola Island. You can picture it as a perfect n x n square. Incredibly, n^2 people live there, each in a perfect 1x1 square. They all have an integer spirit in the range [1, 10^6]. The King died recently and, as is custom, Xorland must be divided into three parts.

Xorlandic people love to apply the Xor operation on their spirits, so it is normal to expect them to use it also to divide the land. Xorland must be divided by two parallel lines. These parallel lines must also be parallel to one side of the square. Each part will be non-empty. To divide the land, this is what they do:

(1) Place two parallel lines inside the square.

(2) Construct a non-empty subset of the spirits of the first part and call it A.

(3) Construct a non-empty subset of the spirits of the second part and call it B.

(4) Construct a non-empty subset of the spirits of the third part and call it C.

(4) Apply the Xor operation on A, on B and on C.

(5) Find the value of Xor(A) + Xor(B) + Xor(C) and call it SUM.

(6) Eat and Drink joyfully for SUM days straight.

Between us, Xorlandic people LOVE eating and drinking! That is why they want to find the partition that yields the greatest sum. Help them! Write a program that finds this number.

Input

The first line of input contains N (3 <= N <= 5), the length of the sides of the squared area. Then follow N lines, each bearing a spirit. Each spirit will be a positive integer in the range [1, 10^6].

Output

Output the greatest sum possible.

Sample Cases

Input
3
1 1 1
2 2 2
3 3 3

Output
9

In this case, the optimal choice is to divide vertically. Column 1 is {1, 2, 3}; Column 2 is {1, 2, 3} and Column 3 is {1, 2, 3}. Taking A = {3}, B = {3} and C{3} we get 3 * Xor{3} = 9, the optimal answer. Note that other subsets may yield 9 as well.


hide comments
miodziu: 2014-02-05 05:51:56

Now I got AC :-) Thanks for explanation Mitch.

Mitch Schwartz: 2014-02-05 05:51:56

Letting A={1,2,3} would result in Xor(A)=0 as you wrote; to get the maximal value of 3, we choose either A={3} or A={1,2}. Same with B and C. Xor is defined in the usual way (extended from binary to n-ary unambiguously because Xor is commutative).

Last edit: 2014-02-05 05:50:32
miodziu: 2014-02-05 05:51:56

I still can't understand, what is Xor(A)?

Luis Miguel Ruiz: 2014-02-05 05:51:56

3+3+3. XOR(x) could be only one number of the subset x. You want the maximum value possible

Last edit: 2014-01-21 13:10:52
miodziu: 2014-02-05 05:51:56

When we divide vertically, A=B=C={1,2,3}, but 1 XOR 2 XOR 3 = 0, so the sum=0.
But when divide hirizontally, A={1,1,1}, B={2,2,2}, C={3,3,3}, and XOR(A)=1, XOR(B)=2, XOR(C)=3, and sum = 1+2+3=6
How the output 9 is possible?


Added by:Olson Ortiz
Date:2013-01-01
Time limit:0.411s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Olimpiada de ProgramaciĆ³n PUCMM ACM-ISC 2013