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.
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.
The output should contain exactly one integer, the maximum number of skill points Peanut can have at the end of the game.
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.
0 3 4 5
4 1 2 7
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.