20370번 - 공정한 게임

문제

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

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

입력

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

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

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

출력

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

제한

힌트