[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 A_{ij} represents the experience of the monster at grid(i,j). If A_{ij}=0, there is no monster at grid(i,j).

#### Output

One integer, the value of max experience.
#### Samples

#### Source

第九届山东省赛

Then n lines follow. In each line there are n integers, and A

A_{ij}≤10^{9}

Time Limit: | 6000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |