skillmoves

Problem Description

Peanut is trying out a new, and very simple game. He starts off with 0 skill points in this game. There are a total of N skill moves he can choose to perform, with the ith skill move requiring a minimum of Mi skill points to perform, and earns him Ei skill points if he performs it. Each skill move can only be performed once.

Peanut does not have all the time in the world, and so can only perform up to K skill moves before he gets tired. Help him figure out what is the maximum number of skill points he can get by the end of the game.

Input

The first line of input will contain two integers, N and K.

The second line of input will contain N integers, representing the array M.

The third line of input will contain N integers, representing the array E.

Output

The output should contain exactly one integer, the maximum number of skill points Peanut can have at the end of the game.

Limits

For all subtasks: 1 ≤ K ≤ N ≤ 300 000, 0 ≤ Mi, Ei ≤ 109.

Subtask 1 (37%): 1 ≤ K ≤ N ≤ 1000.

Subtask 2 (19%): Mi = 0.

Subtask 3 (44%): No additional constraints.

Sample Input

4 3
0 3 4 5
4 1 2 7

Sample Output

13

Explanation

Peanut can first start by performing move 1 (requiring 0 points), giving him 4 points.

He then chooses to perform move 3 (requiring 4 points), giving him 2 points.

Lastly, he performs move 4 (requiring 5 points), giving him 7 points.

Therefore, in total he would have gained 4+2+7=13 points.


Submitting .cpp to 'skillmoves'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 24
Your best score: 0
Source: RI November Course Stage 2 Selection Test 2019
Editorial: 1

Subtask Score
1 37
2 19
3 44
4 0