100.0% (29/29)

58.8% (57/97)

# Description

After wining every informatics competition in the world, Peter the Hacker decided to try a different type of challenge. He registered in the Russian web site for online competitions in cryptography and locksmith “VerhShifr” and soon he has arrived in Moscow, participating in the finals.
During one of the excursions that the organizers prepared, the group visited a large museum for Matryoshka dolls – traditional Russian nested toys. Inside the museum, there was a strange labyrinth. Its rooms and the labyrinth itself were squares and their walls were parallel to the north-south and east-west axes. Each chamber had four doors – one on each side. The entrance to the labyrinth was in the most northwestern room and the exit – in the most southeastern.
The Russian national team in ciphers prepared an interesting game for their opponents. In each room, they left a single empty Matryoshka doll with unique size. Everyone had to go through the labyrinth and collect as many toys as possible but under one condition. Every time someone picks a doll, he has to nest all the dolls he has into the new one. Of course, the contestants could decide whether to pick a Matryoshka (if it is bigger than the last one) or to continue to the next room. To make things even harder, the genius of the safes – Metr Pitrichev – had modified the doors so that from a room one can move only to the rooms to the south and to the east.
Peter, of course, was not such a master with the locks and could not deal with the modification. Instead, he wrote a program, which can find the best way to collect as many toys as possible. Can you do that, too? Write a program matr that calculates the maximum amount of Matryoshka dolls, which Peter the Hacker can collect for a given configuration of rooms.

# Input Format

On the standard input you will get a single integer $N$ $(1 < N < 1000)$, followed by $N$ rows with $N$ numbers (one for each room). Every number describes the size of the toy inside the corresponding chamber. The rows are ordered from north to south (the first row is the most northern) and the columns are ordered from west to east (the first number on every row is the most western). A Matryoshka doll fits into another if it has smaller size than the second one. The sizes will be integer numbers in $[ 1, N^ {2} ]$ and will not repeat.

# Output Format

On the standard output, you should print a single integer – the maximum amount of toys that Peter the Hacker can collect following the rules.

3
9 4 1
6 5 7
2 3 8

4
1 15 4 5
2 10 9 16
14 7 8 3
13 6 11 12

4

6

# Hints

※2009/02/21 加入題目翻譯 by hallogameboy , 感謝 math120908
※2020/10/20 Fixed $\LaTeX$ by Seanliu

# Problem Source

No. Testdata Range Score
1 0 4
2 1 4
3 2 4
4 3 4
5 4 4
6 5 4
7 6 4
8 7 4
9 8 4
10 9 4
11 10 4
12 11 4
13 12 4
14 13 4
15 14 4
16 15 4
17 16 4
18 17 4
19 18 4
20 19 4
21 20 20

# Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 131072 262144 1
1 1500 131072 262144 2
2 1500 131072 262144 3
3 1500 131072 262144 4
4 1500 131072 262144 5
5 1500 131072 262144 6
6 1500 131072 262144 7
7 1500 131072 262144 8
8 1500 131072 262144 9
9 1500 131072 262144 10
10 1500 131072 262144 11
11 1500 131072 262144 12
12 1500 131072 262144 13
13 1500 131072 262144 14
14 1500 131072 262144 15
15 5900 131072 262144 16
16 5900 131072 262144 17
17 5900 131072 262144 18
18 5900 131072 262144 19
19 5900 131072 262144 20
20 5900 131072 262144 21