Suppose you are working on a project and you need to finish at most k distinct projects before an IPO. You are given n projects where the ith project has a pure profit profits[i] and a minimum capital capital[i] is needed to start the ith project.

Initially, you have w capital. When you finish a project, you get its pure profit added to your capital.

Return the maximum capital you can accumulate after finishing at most k distinct projects.

Example 1:

Input:
2 0
1 2 3
0 1 1
Output: 4

Example 2:

Input:
3 0
1 2 3
0 1 2
Output: 6

Constraints:

• 1 ≤ k ≤ 10⁵
• 0 ≤ w ≤ 10⁹
• 1 ≤ n ≤ 10⁵

Input format: First line: k w. Second line: profits. Third line: capital.

Output format: Maximum capital.