19578번 - 가뭄(Large)

문제

가뭄에 찌든 신촌을 위해서 국렬이는 신촌에 비를 내렸다. 가뭄(Small)에서 충분히 비를 내리게 해서 홍익대학교와 이화여자대학교는 가뭄을 해결하였다. 그러나 신촌역 근방이라 제일 크게 피해를 본 연세대학교와 서강대학교는 가뭄이 완전히 해결되지 않았기 때문에 국렬이는 이 두 대학교에 다시 비를 내리게 할 것이다.

각 대학교의 구역들은 N칸으로 구분되어 있으며 연세대학교의 구역은 A₁ ~ A_N, 서강대학교의 구역은 B₁ ~ B_N으로 구분되어 있다. A_i 구역에 a_i cm 만큼 비를 내리게 하고, B_j 구역에는 b_j cm 만큼 비를 내리게 할 것이다. 여기서 나오는 a_i와 b_j는 음이 아닌 실수다.

그러나 국렬이는 연세대학교 학생이고 인성이 매우 나쁘다. 때문에 비겁하게 연세대학교에 비를 더 많이 내리게 할 것이다. 당연히 서강대학교 측에서는 항의가 올 것이기 때문에 a_i − b_j cm가 c_i,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번째 정수는 c_i,j를 의미한다. (1 ≤ c_i,j ≤ 100)

출력

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

제한

힌트