시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 33 15 15 88.235%

문제

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

각 대학교의 구역들은 N칸으로 구분되어 있으며 연세대학교의 구역은 AAN, 서강대학교의 구역은 BBN으로 구분되어 있다. Ai 구역에 ai cm 만큼 비를 내리게 하고, Bj 구역에는 bj cm 만큼 비를 내리게 할 것이다. 여기서 나오는 ai와 bj는 음이 아닌 실수다.

그러나 국렬이는 연세대학교 학생이고 인성이 매우 나쁘다. 때문에 비겁하게 연세대학교에 비를 더 많이 내리게 할 것이다. 당연히 서강대학교 측에서는 항의가 올 것이기 때문에 aibj 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$의 최댓값을 소수 첫째 자리에서 반올림해 출력한다.

예제 입력 1

2
2 1
1 2

예제 출력 1

2

a= 3, a= 2, b= 1, b= 2일 때 값이 최대가 된다.

예제 입력 2

3
2 3 2
3 4 4
2 3 2

예제 출력 2

8

a= 4, a= 5, a= 4, b= 2, b= 1, b= 2일 때 값이 최대가 된다.