Summa Summarum
면접 대비시간 제한5초메모리 제한1024 MB
두 정수 리스트에서 원소를 하나씩 정확히 한 번 교환해 두 합의 차이를 가장 작게 만드는 값을 구합니다.
문제
안데르스와 베아트리스는 각자 정수 목록을 가지고 있다. 두 목록에 들어 있는 정수의 개수는 같다. 안데르스는 자기 목록의 모든 수의 합이 베아트리스 목록의 모든 수의 합과 같아지기를 꿈꾼다. 그래야 베아트리스가 감탄할 것이기 때문이다. 안데르스는 대학에서 여러 해 공부해서 이것이 항상 성립하지는 않는다는 것을 안다. 그래도 그에게는 꿈에 가까워질 계획이 있다.
안데르스는 두 합의 차이를 가능한 한 작게 만들고 싶어 한다. 베아트리스가 보지 않을 때, 안데르스는 자기 목록의 수 하나를 베아트리스 목록의 수 하나와 교환할 수 있다. 의심을 받지 않도록 이런 교환은 한 번만 한다.
안데르스가 정확히 한 번 교환해야 한다고 할 때, 그가 만들 수 있는 두 합의 최소 차이는 얼마인가?
입력
첫 줄에 정수 이 주어진다. 은 안데르스의 목록과 베아트리스의 목록에 들어 있는 정수의 개수다. 둘째 줄에는 안데르스의 목록을 나타내는 개의 정수가, 셋째 줄에는 베아트리스의 목록을 나타내는 개의 정수가 주어진다. 입력의 모든 정수 는 를 만족한다.
출력
안데르스가 위에서 설명한 교환을 한 뒤, 안데르스 목록의 합과 베아트리스 목록의 합 사이의 최소 차이를 정수 하나로 출력한다.
제한
힌트
안데르스의 목록이 이고 베아트리스의 목록이 라고 하자. 안데르스의 목록에 있는 5 하나를 베아트리스 목록의 4 하나와 교환하면 두 목록은 똑같은 수를 갖게 된다. 두 합은 모두 15가 되므로 답은 0이다.