Hide

Problem L
Lemonade

Simon just wanted to make cute robot dogs to keep as pets, but they turned against him. They have currently taken over his garden — where they are preparing for world domination. The robot dogs are (obviously) fueled by lemonade, and they have built a small lemonade factory using lemons from Simon’s garden. Simon needs to act now in order to stop them from producing enough lemonade for world domination!

Unfortunately, the robot dogs guard the lemon trees at all times and are patrolling the factory at regular intervals. This makes it hard for Simon to sabotage, but after having observed them for a while he might have found a way. Every ten minutes there’s a small time window in which a tap to the main mixing tank is out of sight of the patrolling dogs. In that small window of time Simon can run up to the mixing tank with a hose and empty the tank. Once the tap is opened it can’t be closed before the tank is emptied. The mixing tank can be assumed to not be filled or emptied by anyone else during this small window of time. Even when faced with the threat of robot dog world dominance, Simon doesn’t want any good lemons to go to waste. Hence, he will empty the content of the mixing tank into his own tank inside his house, where it will be safe from the robot dogs. This tank will initially be empty and have a capacity of $N$ liters.

From his previous scouting, Simon have figured out that he has $M$ consecutive opportunities to empty the mixing tank. The dogs have unlimited amount of water, so the goal is to steal as much lemonade juice as possible. The content of the mixing tank changes regularly as part of a complex lemonade production process. Let $v_ i$ and $l_ i$ be the total volume of the content and the amount of lemon juice respectively in the mixing tank for the $i$th ($1 \leq i \leq M$) opportunity to empty it. The volume $v_ i$ is in liters and $l_ i$ is in number of lemons worth of juice. Then the volume and amount of lemon juice changes according to

\begin{equation*} \begin{split} v_ i & = ((a*i + b*v^*_{i-1}) \bmod c) + 1 \\ l_ i & = (d*i + e*v^*_{i-1}) \bmod f \end{split}\end{equation*}

Where $a,b,c,d,e,f$ are constants, while $v^*_ i$ is the content volume Simon has or has not emptied the mixing tank at the $i$th opportunity. If the mixing tank was not emptied we simply get $v^*_ i = v_ i$, but if it is emptied we get $v^*_ i = 0$. In other words, whether Simon chooses to empty the mixing tank or not at any given opportunity will affect the content volume and amount of lemon juice at the next opportunity.

Simon wants you to help him find out at which opportunities he should empty the mixing tank to maximize the amount of lemon juice he will steal from the robot dogs, while at the same time respect the capacity of his in-house tank.

Input

The first line will contain two positive integers, $N$ and $M$. And the second line will contain eight positive integers, $a$, $b$, $c$, $d$, $e$, $f$ and $v^*_0$.

Output

Print the maximal amount of lemon juice Simon is able to steal from the robot dogs.

Limits

  • $1 \leq N, M, c, f \leq 150$

  • $1 \leq a,b,d,e \leq 1\, 000\, 000$

  • $0 \leq v^*_0 \leq c$

Sample Explanation

In Sample 1, at Simon’s first opportunity, there is $(7 \times 1 + 1 \times 0) \bmod 10 + 1 = 8$ liters of content and $(1 \times 1 + 1 \times 0) \bmod 11 = 1$ lemons worth of juice. If he chooses to empty the tank, there will be $(7 \times 2 + 1 \times 0) \bmod 10 + 1 = 5$ liters of content at next opportunity. And so he wouldn’t be able to empty the mixing tank the second time because $7 + 5 = 12$ goes beyond the capacity of his in-house tank. Ending up with only $1$ lemon worth of juice. On the other hand, if he does not empty the mixing tank at the first opportunity, the mixing tank will have $(7 \times 2 + 1 \times 8) \bmod 10 + 1 = 3$ liters of content and $(1 \times 2 + 1 \times 8) \bmod 11 = 10$ lemons worth of juice at the second opportunity. So the optimal plan is to wait out the first opportunity and then empty the one liter containing $10$ lemons worth of juice at the second opportunity.

Sample Input 1 Sample Output 1
10 2
7 1 10 1 1 11 0
10

Please log in to submit a solution to this problem

Log in