[Hidden ☆ before use]

#### 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 × 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).
Aij≤109

#### Output

One integer, the value of max experience.

#### Samples

Input Copy
2
2 0
1 8

Output
2


#### Source

##### Problem Information

 Time Limit: 6000MS (C/C++,Others×2) Memory Limit: 128MB (C/C++,Others×2) Special Judge: No AC/Submit: 1 / 1 Tags:
##### Contests involved

 1017. 2018 SD ACM