### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

This problem can be solved by using DFS (Depth First Search). The number of states is much smaller than **rN**, and it works with **O(r * N *** the number of states) time, where r = 4 is derived from the values of the minimal **X** 10 and the required magical powers 666.

Some basic observations are here. Let **ki** be the minimal non-negative integer **k** such that **Mi / 3k ≤ 666**. We can consider that Ciel uses the help of the Evilbook for the i-th chef only before defeating the i-th chef. If Ciel already has enough magical power, Ciel must use at least max(0, **ki** - 1) helps before defeating the i-th chef, because Ciel may get at least 666 magical power after using **ki** - 1 helps if **ki** > 0. And Ciel must not use more than **ki + r** - 1 helps before defeating the i-th chef, because 666 / 3**r-1** - (**r**-1) * **X** ≤ 0, so if used, Ciel’s magical power will be decreased. Therefore, when Ciel has no more than 666 magical power, each chef has only r states, undefeated, defeated with **ki** helps, defeated with ki + 1 helps, …, defeated with **ki + r** - 1 helps. So the total number of states is at most **rN.**

If the number of states is just 4**N** (at most 410 = 1048576), it seems a bit large. Indeed, we can check the number of states is much smaller. For example, if **Mi** ≤ 666/3, then the i-th chef has at most 3 states, because Ciel uses at most 2 helps for i-th chef. So, let **Mi** > 666/3, then at most 2 chef can have the state “defeated with **ki** helps”, because otherwise Ciel has at least 666 magical power. Therefore, we can prove that the number of states is at most 3**N** + **N** * 3**N-1** + **N * (N**-1) / 2 * 3N-2 (at most 310 + 10 * 39 + 10 * 9 / 2 * 38 = 551124). Of course, the true number of states is smaller than it.

**O(r * N** * the number of states) time solutions can be accepted in the problem. If we would like to get more fast solutions, some prunings work fine. For example, let MaxEffiency be the maximal value of **Mi / Ci** over all undefeated chefs. Then we can use the lower bound of the answer, NowEffort + (666 - NowMagicalPower) / MaxEffiency. See the setter’s solution for details.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.