masters[i] is the skill level of master i. Orders have come in: orders[j] = [need, pay] means order j requires a skill of exactly need and pays pay.
Each master completes at most one order, and only one whose need equals their skill. In addition, one generalist is on shift today: they can take any single order regardless of its skill requirement. Each order can be completed at most once.
Return the largest total pay you can earn.masters=[2, 2, 5], orders=[[2, 30], [2, 50], [2, 20], [5, 10], [7, 40]] → 130
The two skill-2 masters take the orders paying 50 and 30, the skill-5 master takes the one paying 10. The generalist takes the best remaining order, 40. Total: 130.
masters=[3], orders=[[1, 8], [2, 9]] → 9
No order needs skill 3, and the generalist can take just one order, the one paying 9.
masters=[4, 4], orders=[[4, 6], [4, 6], [4, 6]] → 18
len(masters) ≤ 10⁵masters[i] ≤ 10⁹len(orders) ≤ 10⁵orders[j] = [need, pay], 1 ≤ need, pay ≤ 10⁹masters=[2, 2, 5], orders=[[2, 30], [2, 50], [2, 20], [5, 10], [7, 40]]
130
Run checks the first 3 tests in your browser. Submit checks all 207 tests on the server, hidden ones included.