[Solution] FTL Codeforces Solution | Solution Codeforces

E. FTL

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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$1$ and 2$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 𝑝1+𝑝2$p_1+p_2$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes 0$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

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

The second line contains two integers 𝑝2$p_2$ and 𝑡2$t_2$ (2≤𝑝2≤5000$2\le p_2\le 5000$; 1≤𝑡2≤1012$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≤ℎ≤5000$1\le h\le 5000$; 1≤𝑠<min(𝑝1,𝑝2)$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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 destroy an enemy spaceship.

Output

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

Note

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

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