Fewest Wounds in Battle

Hard

A hero fights n monsters. Monster i deals attack[i] damage to the hero every second while it is alive, and it has toughness[i] health points. Each second goes like this: first every living monster hits the hero, then the hero picks one living monster and takes strike health points off it. A monster dies once its health drops to zero or below. Return the smallest total damage the hero can take before all the monsters are dead.

Example 1

strike=3, attack=[2, 5], toughness=[3, 7] → 22

The first monster falls after one hit, the second needs three. Starting with the first, the hero takes 7 damage in the first second and 5 in each of the next three: 7 + 15 = 22. The other order would cost 7·3 + 2 = 23.

Example 2

strike=10, attack=[4], toughness=[25] → 12

The monster needs three hits and strikes the hero for 4 in each of those three seconds: 12 in total.

Example 3

strike=2, attack=[1, 3, 2], toughness=[4, 2, 6] → 17

Constraints

1 ≤ strike ≤ 10⁴
1 ≤ n = len(attack) = len(toughness) ≤ 10⁵
1 ≤ attack[i], toughness[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Growing Capital Project by Project Hard Distinct Word Shorthands Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Two Marks in Every Range Hard

Input

strike=3, attack=[2, 5], toughness=[3, 7]

Expected

Run checks the first 3 tests in your browser. Submit checks all 115 tests on the server, hidden ones included.