Drought (Large)

Time limit1sMemory limit1024 MB

Summary

Maximize the sum of a_i minus the sum of b_j over nonnegative reals a and b subject to a_i - b_j <= c_ij, then round the answer to the nearest integer.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Math, Binary search
Solved: No attempts yet

Problem

To relieve the drought-stricken Sinchon, Gukryeol made it rain over Sinchon. In Drought (Small) the rain fell enough that Hongik University and Ewha Womans University were no longer in drought. But Yonsei University and Sogang University, which suffered the most because they sit near Sinchon Station, were not fully relieved, so Gukryeol will make it rain over these two universities again.

The districts of each university are divided into N cells: the districts of Yonsei University are A1 to AN, and the districts of Sogang University are B1 to BN. He will make ai cm of rain fall on district Ai and bj cm of rain fall on district Bj. Here ai and bj are nonnegative real numbers.

However, Gukryeol is a Yonsei University student and has a very bad character. So he cowardly makes more rain fall on Yonsei University. Sogang University will of course protest, so he makes the rain fall such that ai − bj cm does not exceed ci,j cm. The wicked Gukryeol wanted Yonsei University to benefit as much as possible, so he wanted $\sum_{i=1}^{N} a_i - \sum_{j=1}^{N} b_j$ cm to be as large as possible. Find this maximum value.

Input

The first line gives N (1 ≤ N ≤ 200).

From the second line to the N + 1-th line, N positive integers are given. The j-th integer on the (i + 1)-th line means ci,j. (1 ≤ ci,j ≤ 100)

Output

Print the maximum value of $\sum_{i=1}^{n} a_i - \sum_{j=1}^{n} b_j$ , rounded to the nearest integer.

Examples2

Example 1
Input
```
2
2 1
1 2
```
Expected output
```
2
```
Example 2
Input
```
3
2 3 2
3 4 4
2 3 2
```
Expected output
```
8
```