本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden ☆ before use]

1139. Bullet


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
My history solutions

You didn't submit any solution!
Submit your solution

Login Register