팀 배정

사내 해커톤 대회에서 팀 배틀 보안 해커톤을 하기로 했다.

대회는 주어진 보안 서버를 공격(해킹)하는 역할의 팀 A와 방어(보안)하는 역할의 팀 B로 나누어서 진행한다. 참가자는 총 n명이고, 각 참가자의 공격 능력과 방어 능력은 검증된 사내 테스트를 통해 수치화 되어있다.

참가자는 1부터 n까지 번호가 매겨져 있고, Ai, Bi는 양의 정수로 참가자 i의 공격 능력과 방어 능력을 의미한다.

n명의 참가자를 팀 A와 팀 B로 아래 조건을 지키면서 나누어야 한다.

• 두 팀에 배정된 참가자 수의 차이는 k 이하가 되어야 한다.
• 각 참가자는 두 팀 중 하나에 반드시 속해야한다.
• 위의 두 조건을 만족하는 모든 팀 배정 방법 중, 팀 A에 배정된 참가자들의 공격 능력 총 합과 팀 B에 배정된 참가자들의 방어 능력치 총 합이 최대가 되어야 한다.

예를 들어, n = 3, k = 1이고, 세 참가자의 공격 능력과 방어 능력이 아래와 같은 경우를 살펴보자.

• A1 = 1, B1 = 100
• A2 = 100, B2 = 99
• A3 = 80, B3 = 95

k = 1이기 때문에, 팀 A와 팀 B에는 각각 1명과 2명이 배정되어야 한다.

총 여섯 가지 방법이 가능하며 팀 구성과 능력치의 합은 아래와 같다.

1. 팀 A: [1], 팀 B: [2, 3], 능력치의 합 = A1 + B2 + B3 = 195
2. 팀 A: [2], 팀 B: [1, 3], 능력치의 합 = A2 + B1 + B3 = 295
3. 팀 A: [3], 팀 B: [1, 2], 능력치의 합 = A3 + B1 + B2 = 279
4. 팀 A: [2, 3], 팀 B: [1], 능력치의 합 = A2 + A3 + B1 = 280
5. 팀 A: [1, 3], 팀 B: [2], 능력치의 합 = A1 + A3 + B2 = 180
6. 팀 A: [1, 2], 팀 B: [3], 능력치의 합 = A1 + A2 + B3 = 196

두 번째 방법이 가장 높은 능력치 합을 가진다.

n, k, 그리고 각 참가자의 공격과 방어 능력치가 주어졌을 때, 가능한 모든 팀 배정 방식 중에서 능력치 합의 최댓값을 구해보자.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 n과 k가 공백으로 구분되어 주어진다. 둘째 줄에는 참가자의 공격 능력을 나타내는 A1, A2, ..., An이 주어지고, 셋째 줄에는 방어 능력을 나타내는 B1, B2, ..., Bn이 주어진다.

각 테스트 케이스 마다 능력치 합의 최댓값을 한 줄에 하나씩 출력한다.

• 1 ≤ T ≤ 10
• 3 ≤ n ≤ 100,000
• 1 ≤ k ≤ n-2
• 1 ≤ Ai, Bi ≤ 1,000,000

능력치 총 합이 231-1 보다 클 수 있다.