oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

skillmoves Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

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.

Tags

Greedy, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
137211s256MBMinimum
219201s256MBMinimum
344611s256MBMinimum
4011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o skillmoves -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.