617. IPO
0
Hard
Coding Blocks is preparing for its upcoming IPO and wants to increase its capital by working on projects. However, due to limited resources, they can only complete a maximum of k distinct projects before the IPO. Your task is to help Coding Blocks design the most effective strategy to maximize their total capital after completing at most k distinct projects.
You are given n projects, each with a pure profit (profits[i]) and a minimum capital requirement (capital[i]) to start. Initially, you have w capital. Upon completing a project, you will receive its pure profit, which will be added to your total capital.
Your goal is to select a list of at most k distinct projects from the given projects in order to maximize your final capital. Print the final maximized capital.
The answer will always be a 32-bit signed integer.
Input Format
The first line contains the value of k.
The second line contains the value of w.
The third line contains the size of the profits array.
The fourth line contains the elements of the profits array.
The fifth line contains the size of the capital array.
The sixth line contains the elements of the capital array.
Output Format
Print the final maximized capital as an integer.
Example
Input
2
0
3
1 2 3
3
0 1 1
Output
4
Constraints
1 <= k <= 10^5
0 <= w <= 10^9
n == profits.length
n == capital.length
1 <= n <= 10^5
0 <= profits[i] <= 10^4
0 <= capital[i] <= 10^9
Loading...
View Submissions
Console