Bullet

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

In GGO, a world dominated by gun and steel, players are fighting for the honor of being the strongest gunmen. Player Shino is a sniper, and her aimed shot kills one monster at a time. Now she is in an $n \times n$ map, and there are monsters in some grids. Each monster has an experience. As a master, however, Shino has a strange self-restrain. She would kill at most one monster in a column, and also at most one in a row. Now she wants to know how to get max experience, under the premise of killing as many monsters as possible.

Input

The first line contains an integer $n$. (n<=500)
Then n lines follow. In each line there are n integers, and $Aij$ represents the experience of the monster at grid $(i,j)$. If $Aij=0$, there is no monster at grid $(i,j)$.

The experience is the minimal experience of all the monster which are killed.

It guaranteed that the maximum of the experience of the monster is not larger than 10^9

Output

One integer, the value of max experience.

Sample Input

2
2 0
1 8

Sample Output

2

Source

“浪潮杯”山东省第九届ACM大学生程序设计竞赛（感谢山东财经大学）