CF1662J.Training Camp

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?

你正在组织一场训练营，向孩子们教授算法。共有 $n^2$ 名孩子，排列成一个 $n \times n$ 的方阵。每名孩子的年龄在 $1$ 到 $n$ 岁之间（含端点），且同一行或同一列中的任意两名孩子的年龄均不相同。

你需要恰好选出 $n$ 名孩子参加编程竞赛，要求：每行恰好选一名孩子，每列也恰好选一名孩子。此外，未被选中的孩子必须满足以下条件之一：其年龄严格大于其所在行与所在列中被选中的两名孩子的年龄，或者严格小于这两名被选中孩子的年龄（否则他们会抱怨）。注意，总存在满足这些要求的 $n$ 人选择方案（例如，选择 $n$ 名年龄完全相同的孩子即可）。

在训练营期间，你观察到部分孩子擅长编程，其余则不擅长。在满足上述所有要求的前提下，你最多能选出多少名擅长编程的孩子？

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 \lt j'\le n$, and $a_{i,j} \ne a_{i',j}$ for any $1\le i \lt 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.

第一行包含一个整数 $n$（$1 \leq n \leq 128$），表示网格的大小。

接下来的 $n$ 行描述孩子们的年龄。具体而言，第 $i$ 行包含 $n$ 个整数 $a_{i,1},\, a_{i,2},\, \dots,\, a_{i,n}$（$1 \le a_{i,j} \le n$），其中 $a_{i,j}$ 表示第 $i$ 行、第 $j$ 列的孩子的年龄。题目保证同一行或同一列上的任意两个孩子年龄均不相同，即对任意 $1\le i\le n$、$1\le j \lt j'\le n$，有 $a_{i,j} \ne a_{i,j'}$；且对任意 $1\le i \lt i'\le n$、$1\le j\le n$，有 $a_{i,j} \ne a_{i',j}$。

接下来的 $n$ 行描述孩子们的编程能力。具体而言，第 $i$ 行包含 $n$ 个整数 $c_{i,1},\, c_{i,2},\, \dots,\, c_{i,n}$（$c_{i,j} \in \{0,\, 1\}$），其中若第 $i$ 行、第 $j$ 列的孩子擅长编程，则 $c_{i,j}=1$；否则 $c_{i,j}=0$。

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

输出在满足所有要求的前提下，最多能选出多少名擅长编程的孩子。

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.

在第一个样例中，无法同时选择两名擅长编程的小孩（分别位于第 $1$ 行第 $1$ 列、以及第 $2$ 行第 $3$ 列），因为那样就必须同时选择第 $3$ 行第 $2$ 列的小孩；此时将有两名小孩提出抱怨（分别是第 $1$ 行第 $2$ 列和第 $3$ 行第 $1$ 列的小孩）。

一种包含 $1$ 名擅长编程的小孩的有效选择方案是：选出全部 $3$ 名年龄为 $1$ 岁的小孩。

在第二个样例中，共有 $10$ 种满足要求的 $n$ 名小孩的选择方案，且每种方案均恰好选出 $2$ 名擅长编程的小孩。