/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は H 行 W 列のグリッドを持っています。上から i 行目 (1 \leq i \leq H)、左から j 列目 (1 \leq j \leq W) のマスを (i, j) と表します。マス (i, j) の値は整数 A_{i,j} です。
高橋君は、行の集合 R \subseteq \{1, 2, \ldots, H\} と列の集合 C \subseteq \{1, 2, \ldots, W\} を自由に選びます。R, C はそれぞれ空集合でも構いません。
マス (i, j) が塗りつぶされるとは、i \in R または j \in C の少なくとも一方が成り立つことをいいます。塗りつぶされたマスの値の合計を S とします。すなわち、
S = \sum_{\substack{(i,j) \\ i \in R \text{ or } j \in C}} A_{i,j}
です。塗りつぶされるマスが存在しない場合（R = C = \emptyset の場合）は S = 0 とします。
R と C のすべての選び方を考えたときの S の最大値を求めてください。
> 補足（包除原理による等価な表現）： 上の S は次のようにも計算できます。
>
> S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} \sum_{j \in C} A_{i,j}
制約
- 1 \leq H \leq 19
- 1 \leq W \leq 19
- -10^9 \leq A_{i,j} \leq 10^9
- 入力はすべて整数である
入力
入力は以下の形式で与えられます。
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
1 行目にはグリッドの行数 H と列数 W が、2 行目以降の H 行には各マスの値 A_{i,j} が、それぞれスペース区切りで与えられます。
出力
S の最大値を一行で出力してください。
入力例 1
2 3 5 -2 4 -3 6 -1
出力例 1
13
入力例 2
3 3 -1 -2 -3 -4 -5 -6 -7 -8 -9
出力例 2
0
入力例 3
5 6 3 -5 2 7 -1 4 -4 6 -2 1 8 -3 5 -3 0 -6 4 2 -7 2 9 -1 -5 6 1 -8 3 5 -2 7
出力例 3
50
入力例 4
8 8 1000000000 -1000000000 5 -7 8 -9 10 -11 -1000000000 1000000000 -6 7 -8 9 -10 12 13 -14 1000000000 -1000000000 15 -16 17 -18 -19 20 -1000000000 1000000000 -21 22 -23 24 25 -26 27 -28 1000000000 -1000000000 29 -30 -31 32 -33 34 -1000000000 1000000000 -35 36 37 -38 39 -40 41 -42 1000000000 -1000000000 -43 44 -45 46 -47 48 -1000000000 1000000000
出力例 4
4000000321
入力例 5
1 1 1000000000
出力例 5
1000000000
Score : 433 pts
Problem Statement
Takahashi has a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as (i, j). The value of cell (i, j) is the integer A_{i,j}.
Takahashi freely chooses a set of rows R \subseteq \{1, 2, \ldots, H\} and a set of columns C \subseteq \{1, 2, \ldots, W\}. Each of R and C may be the empty set.
A cell (i, j) is painted if at least one of i \in R or j \in C holds. Let S be the sum of the values of the painted cells. That is,
S = \sum_{\substack{(i,j) \\ i \in R \text{ or } j \in C}} A_{i,j}
If no cells are painted (i.e., R = C = \emptyset), then S = 0.
Find the maximum value of S over all possible choices of R and C.
> Note (equivalent expression using inclusion-exclusion principle): The above S can also be computed as follows.
>
> S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} \sum_{j \in C} A_{i,j}
Constraints
- 1 \leq H \leq 19
- 1 \leq W \leq 19
- -10^9 \leq A_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given in the following format.
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
The first line contains the number of rows H and the number of columns W of the grid. The following H lines contain the values A_{i,j} of each cell, separated by spaces.
Output
Print the maximum value of S in a single line.
Sample Input 1
2 3 5 -2 4 -3 6 -1
Sample Output 1
13
Sample Input 2
3 3 -1 -2 -3 -4 -5 -6 -7 -8 -9
Sample Output 2
0
Sample Input 3
5 6 3 -5 2 7 -1 4 -4 6 -2 1 8 -3 5 -3 0 -6 4 2 -7 2 9 -1 -5 6 1 -8 3 5 -2 7
Sample Output 3
50
Sample Input 4
8 8 1000000000 -1000000000 5 -7 8 -9 10 -11 -1000000000 1000000000 -6 7 -8 9 -10 12 13 -14 1000000000 -1000000000 15 -16 17 -18 -19 20 -1000000000 1000000000 -21 22 -23 24 25 -26 27 -28 1000000000 -1000000000 29 -30 -31 32 -33 34 -1000000000 1000000000 -35 36 37 -38 39 -40 41 -42 1000000000 -1000000000 -43 44 -45 46 -47 48 -1000000000 1000000000
Sample Output 4
4000000321
Sample Input 5
1 1 1000000000
Sample Output 5
1000000000