Moon Mooing

A full moon casts a spell on the cows, and like their cousins the wolves and coyotes they bay at the moon — mooing instead of howling, of course.

Each moo lasts a certain amount of time. A short moo might last 1; a longer one might last 24, or even 1000000000 or more (cows can really moo when they want to). No moo ever lasts 2^63 or longer.

The cows moo according to a pattern. First, Bessie chooses an integer c (1 ≤ c ≤ 100), the length of the initial moo.

Then, from every moo length found so far, two functions produce new moo lengths (all divisions are integer division, i.e. floor):

f1(x) = a1 * x / d1 + b1
f2(x) = a2 * x / d2 + b2

They keep applying both functions to every new length, maintaining a single sorted list of all distinct moo lengths (duplicates are kept only once).

The cows may moo at most N times (1 ≤ N ≤ 4000000). Determine the N-th value in the sorted list — that is, the length of the longest moo produced within the first N moos.

The constants satisfy: 1 ≤ d1 < a1 ≤ 20, 0 ≤ b1 ≤ 20, 1 ≤ d2 < a2 ≤ 20, 0 ≤ b2 ≤ 20.

For example, suppose c = 3 and N = 10, with:

a1 = 4    b1 = 3    d1 = 3
a2 = 17   b2 = 8    d2 = 2

The first moo length is c = 3. The full list of moo lengths is built like this:

 1. c = 3               ->  3       6. f2(3)  = 17*3/2 + 8  -> 33
 2. f1(3)  = 4*3/3 + 3  ->  7       7. f1(28) = 4*28/3 + 3  -> 40
 3. f1(7)  = 4*7/3 + 3  -> 12       8. f1(33) = 4*33/3 + 3  -> 47
 4. f1(12) = 4*12/3 + 3 -> 19       9. f1(40) = 4*40/3 + 3  -> 56
 5. f1(19) = 4*19/3 + 3 -> 28      10. f1(47) = 4*47/3 + 3  -> 65

The tenth value is 65, which is the answer for this input.

• Line 1: Two space-separated integers c and N.
• Line 2: Three space-separated integers a1, b1, and d1.
• Line 3: Three space-separated integers a2, b2, and d2.

• Line 1: A single integer, the length of the N-th moo.