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.
The first line contains an integer n.
n<=500
Then n lines follow. In each line there are nintegers, 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 109
One integer, the value of max experience.