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 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).