만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Summa Summarum

면접 대비

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

요약
두 정수 리스트에서 원소를 하나씩 정확히 한 번 교환해 두 합의 차이를 가장 작게 만드는 값을 구합니다.
난이도

보통10점 중 5점

유형
이분 탐색, 정렬
정답자
아직 제출이 없습니다

문제

안데르스와 베아트리스는 각자 정수 목록을 가지고 있다. 두 목록에 들어 있는 정수의 개수는 같다. 안데르스는 자기 목록의 모든 수의 합이 베아트리스 목록의 모든 수의 합과 같아지기를 꿈꾼다. 그래야 베아트리스가 감탄할 것이기 때문이다. 안데르스는 대학에서 여러 해 공부해서 이것이 항상 성립하지는 않는다는 것을 안다. 그래도 그에게는 꿈에 가까워질 계획이 있다.

안데르스는 두 합의 차이를 가능한 한 작게 만들고 싶어 한다. 베아트리스가 보지 않을 때, 안데르스는 자기 목록의 수 하나를 베아트리스 목록의 수 하나와 교환할 수 있다. 의심을 받지 않도록 이런 교환은 한 번만 한다.

안데르스가 정확히 한 번 교환해야 한다고 할 때, 그가 만들 수 있는 두 합의 최소 차이는 얼마인가?

입력

첫 줄에 정수 NN이 주어진다. NN은 안데르스의 목록과 베아트리스의 목록에 들어 있는 정수의 개수다. 둘째 줄에는 안데르스의 목록을 나타내는 NN개의 정수가, 셋째 줄에는 베아트리스의 목록을 나타내는 NN개의 정수가 주어진다. 입력의 모든 정수 XX는 −105≤X≤105-10^5 \leq X \leq 10^5를 만족한다.

출력

안데르스가 위에서 설명한 교환을 한 뒤, 안데르스 목록의 합과 베아트리스 목록의 합 사이의 최소 차이를 정수 하나로 출력한다.

제한

1≤N≤1051 \leq N \leq 10^{5}

힌트

안데르스의 목록이 [5,2,3,5,1][5,2,3,5,1]이고 베아트리스의 목록이 [1,4,3,4,2][1,4,3,4,2]라고 하자. 안데르스의 목록에 있는 5 하나를 베아트리스 목록의 4 하나와 교환하면 두 목록은 똑같은 수를 갖게 된다. 두 합은 모두 15가 되므로 답은 0이다.

예제3

  1. 예제 1

    입력
    5
    5 2 3 5 1
    1 4 3 4 2
    
    예상 출력
    0
    
  2. 예제 2

    입력
    2
    1 3
    2 2
    
    예상 출력
    2
    
  3. 예제 3

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