Problem Brief

Minimum Cost to Select People for Skill Quotas

FULLTIMEOA

There are n people. Person i has hiring cost costs[i] and may have Skill 1, Skill 2, both skills, or neither skill.

For every K from 1 to n, compute the minimum total hiring cost needed so that the selected subset contains at least K people with Skill 1 and at least K people with Skill 2. A person who has both skills contributes to both counts.

Return an array ans of length n where ans[K - 1] is the minimum cost for that quota, or -1 if it is impossible.

Function Description

Complete the function minimumCostForSkillQuotas in the editor below.

minimumCostForSkillQuotas has the following parameters:

int[] costs: hiring costs for each person
int[] skill1: 1 if the person has Skill 1, else 0
int[] skill2: 1 if the person has Skill 2, else 0

Returns

long[]: the minimum cost for every quota size K = 1..n.

1Example 1

Input

costs = [3, 5, 2, 6], skill1 = [1, 0, 1, 0], skill2 = [0, 1, 1, 0]

Output

[2, 10, -1, -1]

Explanation

For K = 1, hiring only the third person is enough because that person has both skills. For K = 2, the cheapest feasible subset costs 10. Larger quotas are impossible.

2Example 2

Input

costs = [4, 7, 3], skill1 = [1, 0, 1], skill2 = [0, 1, 1]

Output

[3, 14, -1]

Explanation

For K = 1, hiring the third person alone is sufficient. For K = 2, all three people must be hired.