A15047 | 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?

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.