FTL
Contest: Educational Codeforces Round 137 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, dp

Monocarp is playing a video game. In the game, he controls a spaceship and has to destroy an enemy spaceship.

Monocarp has two lasers installed on his spaceship. Both lasers $$$1$$$ and $$$2$$$ have two values:

- $$$p_i$$$ — the power of the laser;
- $$$t_i$$$ — the reload time of the laser.

When a laser is fully charged, Monocarp can either shoot it or wait for the other laser to charge and shoot both of them at the same time.

An enemy spaceship has $$$h$$$ durability and $$$s$$$ shield capacity. When Monocarp shoots an enemy spaceship, it receives $$$(P - s)$$$ damage (i. e. $$$(P - s)$$$ gets subtracted from its durability), where $$$P$$$ is the total power of the lasers that Monocarp shoots (i. e. $$$p_i$$$ if he only shoots laser $$$i$$$ and $$$p_1 + p_2$$$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes $$$0$$$ or lower.

Initially, both lasers are zero charged.

What's the lowest amount of time it can take Monocarp to destroy an enemy spaceship?

Input format:
The first line contains two integers $$$p_1$$$ and $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — the power and the reload time of the first laser.

The second line contains two integers $$$p_2$$$ and $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — the power and the reload time of the second laser.

The third line contains two integers $$$h$$$ and $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s < \min(p_1, p_2)$$$) — the durability and the shield capacity of an enemy spaceship. Note that the last constraint implies that Monocarp will always be able to destroy an enemy spaceship.

Output format:
Print a single integer — the lowest amount of time it can take Monocarp to destroy an enemy spaceship.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, Monocarp waits for both lasers to charge, then shoots both lasers at $$$10$$$, they deal $$$(5 + 4 - 1) = 8$$$ damage. Then he waits again and shoots lasers at $$$20$$$, dealing $$$8$$$ more damage.

In the second example, Monocarp doesn't wait for the second laser to charge. He just shoots the first laser $$$25$$$ times, dealing $$$(10 - 9) = 1$$$ damage each time.

Example input:
5 10
4 9
16 1

Example output:
20

Example input:
10 1
5000 100000
25 9

Example output:
25

Editorial:
At any time, we have three possible choices: wait and shoot the first laser, the second laser and both lasers. Sometimes it makes sense to wait to both because you can deal $$$s$$$ more damage than you would do by shooting both lasers separately.
The first claim: greedy won't work. Maybe there is a sufficiently smart greedy, we weren't able to come up with it. The second claim: bruteforce won't work. The funny thing is that it actually worked on the constraints up to $$$2000$$$, but again, we couldn't code any sufficiently fast one for $$$5000$$$.
Thus, let's try some dynamic programming. Since all the times are huge, we'd want to avoid having them as the states. What is small, however, is the durability of the enemy ship and the number of shots we have to make to destroy it.
Ideally, we'd like to have some $$$dp[i]$$$ — the smallest time to deal $$$i$$$ damage to the enemy ship. This way, $$$dp[n]$$$ would be the answer. Sadly, it's not immediately clear how to get rid of reload times completely. There might be states with different times until the charge with the same damage dealt, and we don't know which of those we want to keep.
Thus, let's make the dp state more complicated. Let $$$dp[i]$$$ be the smallest time it takes to deal $$$i$$$ damage if the last shot was from both lasers at the same time. This way we know the reload times of both lasers — they are full $$$t_1$$$ and $$$t_2$$$.
$$$dp[0] = 0$$$, as moment $$$0$$$ has both lasers zero charged as if after a shot.
What are the transitions? Well, now we have to shoot each laser multiple times, then wait until both are charged and shoot both. Both lasers can now be considered independent of each other.
Let the time between the previous double shot and the next one be some value $$$t$$$. During this time, it never made sense to wait until shooting each laser. So we waited $$$t_1$$$, shot the first laser, waited another $$$t_1$$$, shot again, until we couldn't shoot anymore, since the laser wouldn't recharge in time before the double shot. Same for the second laser. Notice that if both $$$t \mod t_1 \neq 0$$$ and $$$t \mod t_2 \neq 0$$$, then you could just decrease $$$t$$$ by $$$1$$$ and shoot each laser the same number of times. Thus, only $$$t$$$ that are multiples of either $$$t_1$$$ or $$$t_2$$$ are optimal.
Thus, we can iterate over all possible waiting times $$$t$$$. Just iterate over $$$i \cdot t_1$$$ and $$$i \cdot t_2$$$ for all $$$i$$$ from $$$1$$$ to $$$h$$$. Having a fixed $$$t$$$, calculate the number of shots of each laser, calculate the damage, go into the corresponding dp state.
It could also happen that the last shot before destroying the ship wasn't a double one. However, it still follows the same ideas. It means that each laser was shooting non-stop until the ship was destroyed. Thus, the destruction time is still a multiple of either of the reload times.
Overall complexity: $$$O(h^2)$$$.