Summa Summarum

면접 대비

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

요약

길이가 같은 두 정수 목록에서 첫 번째 목록의 원소 하나와 두 번째 목록의 원소 하나를 정확히 한 번 교환해 두 합의 차이의 절댓값을 최소로 만든다.

난이도: 보통10점 중 5점
유형: 정렬, 이분 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Anders och Beatrice har varsin lista med heltal. Dessa två listor innehåller lika många tal. Anders har en dröm. Han har en dröm om att summan av alla tal i hans lista ska vara lika med summan av alla tal i Beatrices lista (för att det skulle göra henne imponerad). Anders har läst flera år på högskolan, så han vet att så inte alltid är fallet. Anders har dock en plan för att komma närmare sin dröm.

Anders vill se till att skillnaden mellan de två summorna är så liten som möjligt. Anders kan ta ett av talen i sin egen lista och byta ut mot ett av talen i Beatrices lista, när hon inte ser det. Observera att han endast vågar göra ett sådant byte, annars blir det för misstänkt.

Givet att han måste göra precis ett sådant byte, vilken är den minimala skillnad mellan summorna som Anders kan åstadkomma?

입력

På första raden i indata står ett heltal $N$ , antalet tal i Anders och Beatrices listor. På andra raden i indata följer en lista med $N$ heltal som beskriver talen i Anders lista. På tredje och sista raden i indata följer en lista med $N$ heltal som beskriver talen i Beatrices lista. För varje tal $X$ i listorna i indata så gäller att $-10^5 \leq X \leq 10^5$ .

출력

Utdata ska bestå av ett heltal: den minimala skillnaden mellan summorna av Anders och Beatrices listor, efter att Anders har utfört bytet som beskrevs ovan.

제한

$1 \leq N \leq 10^{5}$

힌트

Anta att Anders och Beatrices listor är $\[5,2,3,5,1]$ respektive $\[1,4,3,4,2]$ . Om vi tar en femma i den första listan och byter ut mot en fyra i den andra listan så kommer listorna innehålla exakt samma tal. Det innebär att båda summorna kommer vara $15$ , och vi svarar då $0$ .

예제3

예제 1
입력
```
5
5 2 3 5 1
1 4 3 4 2
```
예상 출력
```
0
```
예제 2
입력
```
2
1 3
2 2
```
예상 출력
```
2
```
예제 3
입력
```
4
-6 -12 -2 -7
84 3 50 23
```
예상 출력
```
5
```