Training Camp

题意翻译

有一个 $n\times n$ 的网格，第 $i$ 行第 $j$ 列的数为 $a_{i,j}$，保证 $a_{i,j}$ 为 $1\sim n$ 中的一个整数，保证不存在两个属于同一行或者同一列的格子所填入的数相同。 你要从中选出 $n$ 个格子，其中每行每列恰好选出一个格子。一个方案是合法的，当且仅当对于任意一个没有被选择的格子，要么该格子所填入的数比同一行和同一列所选的格子填入的数都要大，要么比它们都要小，可以证明一定存在合法方案。 格子 $(i,j)$ 有权值 $c_{i,j}\in\{0,1\}$，你需要找到所有合法方案中被选择的格子权值和最大的方案。

题目描述

You are organizing a training camp to teach algorithms to young kids. There are $ n^2 $ kids, organized in an $ n $ by $ n $ grid. Each kid is between $ 1 $ and $ n $ years old (inclusive) and any two kids who are in the same row or in the same column have different ages. You want to select exactly $ n $ kids for a programming competition, with exactly one kid from each row and one kid from each column. Moreover, kids who are not selected must be either older than both kids selected in their row and column, or younger than both kids selected in their row and column (otherwise they will complain). Notice that it is always possible to select $ n $ kids satisfying these requirements (for example by selecting $ n $ kids who have the same age). During the training camp, you observed that some kids are good at programming, and the others are not. What is the maximum number of kids good at programming that you can select while satisfying all the requirements?

输入输出格式

输入格式

The first line contains $ n $ ( $ 1 \leq n \leq 128 $ ) — the size of the grid. The following $ n $ lines describe the ages of the kids. Specifically, the $ i $ -th line contains $ n $ integers $ a_{i,1}, \, a_{i,2}, \, \dots, \, a_{i, n} $ ( $ 1 \le a_{i,j} \le n $ ) — where $ a_{i,j} $ is the age of the kid in the $ i $ -th row and $ j $ -th column. It is guaranteed that two kids on the same row or column have different ages, i.e., $ a_{i,j} \ne a_{i,j'} $ for any $ 1\le i\le n $ , $ 1\le j < j'\le n $ , and $ a_{i,j} \ne a_{i',j} $ for any $ 1\le i < i'\le n $ , $ 1\le j\le n $ . The following $ n $ lines describe the programming skills of the kids. Specifically, the $ i $ -th line contains $ n $ integers $ c_{i,1}, \, c_{i,2}, \, \dots, \, c_{i, n} $ ( $ c_{i,j} \in \{0, \, 1\} $ ) — where $ c_{i,j}=1 $ if the kid in the $ i $ -th row and $ j $ -th column is good at programming and $ c_{i,j}=0 $ otherwise.

输出格式

Print the maximum number of kids good at programming that you can select while satisfying all the requirements.

输入输出样例

输入样例 #1

3
1 2 3
3 1 2
2 3 1
1 0 0
0 0 1
0 0 0

输出样例 #1

1

输入样例 #2

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

输出样例 #2

2

说明

In the first sample, it is not possible to select the two kids good at programming (in row $ 1 $ and column $ 1 $ , and in row $ 2 $ and column $ 3 $ ), because then you would have to select the kid in row $ 3 $ and column $ 2 $ , and in that case two kids would complain (the one in row $ 1 $ and column $ 2 $ , and the one in row $ 3 $ and column $ 1 $ ). A valid selection which contains $ 1 $ kid good at programming is achieved by choosing the $ 3 $ kids who are $ 1 $ year old. In the second sample, there are $ 10 $ valid choices of the $ n $ kids that satisfy the requirements, and each of them selects exactly $ 2 $ kids good at programming.