The Curse of the Frog

Let us strip the story down to the part that actually matters.

Suppose jump type $i$ is used $k_i$ times. Then the number of rollbacks caused by this type is

$$\left\lfloor \frac{k_i}{b_i} \right\rfloor.$$

The order of jumps does not change that count. It also does not change the total rollback distance paid by this type. So for reachability, the frog's exact schedule is mostly noise.

For fixed values $k_i$, the final position has the form

$$\sum_i \text{chosen jump distances} - \sum_i \left\lfloor \frac{k_i}{b_i} \right\rfloor c_i.$$

Each chosen jump distance is any integer from $0$ to $a_i$. Therefore, all possible sums of jump distances form one continuous integer interval from $0$ to $\sum_i k_i a_i$. No gaps, no weird parity garbage.

So with these fixed counts, the frog can reach every integer from

$$-\sum_i \left\lfloor \frac{k_i}{b_i} \right\rfloor c_i$$

to

$$\sum_i k_i a_i - \sum_i \left\lfloor \frac{k_i}{b_i} \right\rfloor c_i.$$

Since $x>0$, the left endpoint is never a blocker. If the maximum reachable position is at least $x$, then $x$ itself is reachable by choosing smaller jump lengths. Nice. The problem becomes: with as few rollbacks as possible, maximize the right endpoint.

Now look at one jump type independently.

With $0$ rollbacks, type $i$ can be used at most $b_i-1$ times. That gives free maximum distance

$$(b_i-1)a_i.$$

Let

$$S = \sum_i (b_i-1)a_i.$$

If $S \ge x$, the answer is immediately $0$.

What happens after that? Every additional rollback for type $i$ lets us use another block of $b_i$ jumps. Those jumps add at most $b_i a_i$, and the rollback subtracts $c_i$. So one rollback spent on type $i$ changes the maximum position by

$$d_i = b_i a_i - c_i.$$

That is the whole game. If $d_i$ is negative, spending rollbacks there is trash. If it is zero, it does not help. If it is positive, it gives that much extra reach per rollback.

To minimize the rollback count, we should always use the type with maximum positive $d_i$:

$$D = \max_i (b_i a_i - c_i).$$

If $D \le 0$ and $S < x$, then the frog can never get farther than the free distance, so the answer is $-1$.

Otherwise, we need the smallest integer $r$ such that

$$S + rD \ge x.$$

So

$$r = \left\lceil \frac{x-S}{D} \right\rceil.$$

That is it. The frog meditated for years and the solution is a two-variable greedy. Brutal.

Why this is optimal: every plan starts with some number of free jumps and some number of rollback-causing blocks. The free part can contribute at most $S$. Each rollback belongs to some type $i$ and can increase the maximum possible position by at most $d_i \le D$. Therefore, any plan with $r$ rollbacks reaches at most $S+rD$. If our formula says fewer than $r$ rollbacks are not enough, then no clever ordering can save it. And using the type that attains $D$ repeatedly achieves that bound, so the answer is exact.

Edge cases:

• If $x \le S$, print $0$.
• If all $b_i a_i-c_i \le 0$ and $x>S$, print $-1$.
• Use 64-bit integers: $x$ is up to $10^{18}$, and the sum of free distances can be around $10^{17}$.

Complexity per test case is $O(n)$, with $O(1)$ extra memory.