Team Assignment

Interview

Time limit0.7sMemory limit256 MB

Summary
Assign each participant to team A (scoring their attack) or team B (scoring their defense) so the team sizes differ by at most k, maximizing the total.
Level

Medium6 of 10

Topics
Greedy, Sorting, Prefix sum, Dynamic programming
Solved
No attempts yet

Problem

A company is holding a team battle security hackathon at its internal hackathon event.

The contest is run by splitting participants into team A, which attacks (hacks) a given security server, and team B, which defends (secures) it. There are n participants in total, and each participant's attack ability and defense ability have been quantified through a verified internal test.

Participants are numbered from 1 to n, and Ai and Bi are positive integers that denote the attack ability and defense ability of participant i.

The n participants must be split into team A and team B under the following conditions.

  • The difference between the number of participants assigned to the two teams must be at most k.
  • Each participant must belong to exactly one of the two teams.
  • Among all team assignments satisfying the two conditions above, the sum of the attack abilities of the participants assigned to team A and the sum of the defense abilities of the participants assigned to team B must be maximized.

For example, consider the case where n = 3, k = 1, and the attack and defense abilities of the three participants are as follows.

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

Since k = 1, teams A and B must be assigned 1 and 2 participants respectively.

Six assignments are possible, and the team compositions and ability sums are as follows.

  1. Team A: [1], Team B: [2, 3], ability sum = A1 + B2 + B3 = 195
  2. Team A: [2], Team B: [1, 3], ability sum = A2 + B1 + B3 = 295
  3. Team A: [3], Team B: [1, 2], ability sum = A3 + B1 + B2 = 279
  4. Team A: [2, 3], Team B: [1], ability sum = A2 + A3 + B1 = 280
  5. Team A: [1, 3], Team B: [2], ability sum = A1 + A3 + B2 = 180
  6. Team A: [1, 2], Team B: [3], ability sum = A1 + A2 + B3 = 196

The second assignment has the highest ability sum.

Given n, k, and each participant's attack and defense abilities, find the maximum ability sum over all possible team assignments.

Input

The first line gives the number of test cases T.

The first line of each test case gives n and k, separated by a space. The second line gives A1, A2, ..., An, the attack abilities of the participants, and the third line gives B1, B2, ..., Bn, the defense abilities.

Output

For each test case, print the maximum ability sum on its own line.

Constraints

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

Hint

The total ability sum can exceed 231-1.

Examples1

  1. Example 1

    Input
    4
5 2
1 2 3 4 5
2 3 4 5 6
5 3
1 2 3 4 5
5 4 3 2 1
5 2
1 3 5 7 9
1 2 3 4 5
3 1
1 100 80
100 99 95
    Expected output
    18
21
24
295