가뭄(Large)

시간 제한1초메모리 제한1024 MB

요약

음이 아닌 실수 a_i와 b_j에 대해 a_i - b_j <= c_ij라는 제약 아래에서 a_i의 합에서 b_j의 합을 뺀 값을 최대화하고, 그 답을 반올림해 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

가뭄에 찌든 신촌을 위해 국렬이는 신촌에 비를 내렸다. 가뭄(Small)에서 비를 충분히 내려 홍익대학교와 이화여자대학교의 가뭄은 해결되었다. 그러나 신촌역 근처라 피해가 가장 컸던 연세대학교와 서강대학교는 가뭄이 완전히 해결되지 않았으므로, 국렬이는 이 두 대학교에 다시 비를 내리려 한다.

각 대학교의 구역은 N칸으로 나뉘어 있으며, 연세대학교의 구역은 A1 ~ AN, 서강대학교의 구역은 B1 ~ BN이다. Ai 구역에는 ai cm만큼 비를 내리고, Bj 구역에는 bj cm만큼 비를 내린다. 여기서 ai와 bj는 음이 아닌 실수다.

그러나 국렬이는 연세대학교 학생이고 인성이 매우 나쁘다. 그래서 비겁하게 연세대학교에 비를 더 많이 내린다. 서강대학교 측에서 당연히 항의할 것이므로, ai − bj cm가 ci,j cm를 넘지 않게 비를 내린다. 나쁜 국렬이는 연세대학교가 최대한 이익을 보기를 바랐기 때문에 $\sum_{i=1}^{N} a_i - \sum_{j=1}^{N} b_j$ cm가 최대가 되기를 원했다. 이 최댓값을 구하여라.

입력

첫 번째 줄에 N(1 ≤ N ≤ 200)이 주어진다.

두 번째 줄부터 N + 1번째 줄까지 N개의 양의 정수가 주어진다. (i + 1)번째 줄의 j번째 정수는 ci,j를 의미한다. (1 ≤ ci,j ≤ 100)

출력

$\sum_{i=1}^{n} a_i - \sum_{j=1}^{n} b_j$ 의 최댓값을 소수 첫째 자리에서 반올림해 출력한다.

예제2

예제 1
입력
```
2
2 1
1 2
```
예상 출력
```
2
```
예제 2
입력
```
3
2 3 2
3 4 4
2 3 2
```
예상 출력
```
8
```