시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 1024 MB 98 12 9 32.143%

문제

2107년, 신작 게임 레전드 오브 리그(LOL)가 출시됐다. 인류는 이미 게임 분야에서 설자리가 없어졌기 때문에, 이 게임도 요즘 다른 게임들과 마찬가지로 로봇들만 플레이할 수 있다. 오늘은 두 로봇 BOT_6584와 BOT_10과의 대결이 성사됐다. 이 게임에는 N개의 캐릭터가 존재하며, 각 플레이어가 K개의 캐릭터를 선택하여 경기를 펼친다. N개의 캐릭터에는 1부터 N 사이의 서로 다른 정수 번호가 매겨져 있다. 캐릭터 (1 ≤ iN)에 대해, BOT_6584는 Ai, BOT_10은 Bi 만큼의 숙련도를 가진다. 게임의 승패에는 캐릭터 숙련도가 결정적인 역할을 하기 때문에, 두 플레이어는 (자신이 고른 캐릭터들의 숙련도 합 - 상대방이 고른 캐릭터들의 숙련도 합)을 최대화하는 방향으로 캐릭터를 선택한다. BOT_6584는 이번 대결에서 캐릭터를 먼저 고르는 아이템을 사용했다. 따라서, BOT_6584가 먼저 K개의 서로 다른 캐릭터를 선택하고, BOT_10이 남은 N-K개의 캐릭터 중 K개를 선택하여 대결하게 된다.

이때. (BOT_6584가 고른 캐릭터들의 숙련도 합 - BOT_10이 고른 캐릭터들의 숙련도 합)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 (2 x K ≤ N ≤ 80,000), (1 ≤ K ≤ 40,000)가 공백으로 구분되어 주어진다.

둘째 줄에는 A(1 ≤ Ai ≤ 109)를 나타내는 N개의 정수가 순서대로 공백으로 구분되어 주어진다.

셋째 줄에는 B(1 ≤ Bi ≤ 109)를 나타내는 N개의 정수가 순서대로 공백으로 구분되어 주어진다.

출력

두 로봇이 (자신이 고른 캐릭터들의 숙련도 합 - 상대방이 고른 캐릭터들의 숙련도 합)을 최대화하는 방향으로 캐릭터를 선택할 때, (BOT_6584가 고른 캐릭터들의 숙련도 합 - BOT_10이 고른 캐릭터들의 숙련도 합)을 나타내는 정수를 출력하라.

예제 입력 1

7 3
1 1 1 1 1 1 1
5 7 9 1 3 5 2

예제 출력 1

-7

BOT_6584는 캐릭터 1, 2, 3을 BOT_10은 캐릭터 5, 6, 7을 고른다.

예제 입력 2

6 2
9 8 7 6 5 4
6 7 8 9 2 3

예제 출력 2

0

출처

University > 인천대학교 > INU 코드페스티벌 2020 J번