Maximize Total Profit by Assigning Chefs to Dishes

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

You are given three integer arrays:

chefSkill: each chef's skill level

dishDifficulty: each dish's difficulty

dishProfit: the profit earned for completing that dish

Rules:

Each chef can complete at most one dish.

A dish can be completed by multiple chefs (dishes are not exclusive).

A chef can only complete dishes with difficulty <= their skill.

Compute the maximum total profit by assigning each chef the best dish they can do.

Example

Input:

chefSkill = [1,2,3]

dishDifficulty = [1,2,3]

dishProfit = [1,2,3] Output:

6

Explanation: each chef picks the most profitable dish they can do.

Typical constraints (you may state/assume during the interview)

1 <= len(chefSkill), len(dishDifficulty), len(dishProfit) <= 2e5

values are non-negative integers and arrays may be unsorted.

Task

Return the maximum total profit as an integer.

Example

Input

3

1 2 3

3

1 2 3

Output

6

Complete solveMaximizeChefDishProfit. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.