BYU15W_2 - Grid Arithmetic

no tags 

Your task is to take an N-by-N matrix and pick numbers that can be added or subtracted from one another to most closely approximate 0. The catch is that you must only use exactly one number in each row and column—no more, no less.

Example

Consider the following matrix where N = 3.

    1   75   10 
   22  500    3
    9  125   50

75 - 22 - 50 = 3 is the correct answer. 10 - 1 - 9 = 0, but 1 and 9 are from the same column. 3 - 1 = 2, but does not use enough numbers.

Input

The first line contains a single positive integer T, representing the number of test cases. T test cases follow. Each test case begins with a line containing a single integer N, representing the size of the matrix. The next N lines each contain N space-separated integers, representing the matrix.

Output

For each test case, output a single line containing the absolute value of the total found that is closest to 0.

Sample

Input
2
2
1 5
4 3
3
1 75 10
22 500 3
9 125 50

Output
1
3

hide comments
lord_poseidon: 2017-10-01 09:35:24

AC in one go, backtracking, assume n <= 10

martin richardt: 2015-11-05 12:06:37

nevermind.

Last edit: 2015-11-05 14:10:54
:D: 2015-04-08 22:35:30

I assert checked that N <= 10, as Rupesh has posted. You can also assume all sums will fit into 32b signed integer.

Fernando Ferreira de Oliveira [USJT]: 2015-03-30 17:13:58

What is the maximum value of N?

[themighty] deathsurgeon: 2015-03-29 22:49:53

My AC solution assumes n<=10

Mitch Schwartz: 2015-03-29 12:55:37

Please include constraints.


Added by:BYU Admin
Date:2015-03-28
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA