Mooing Madness

A full moon casts a spell on the cows: they moo at the moon!

Each moo lasts a certain amount of time. A cow’s initial moo lasts for an integer duration c (with 1 ≤ c ≤ 100). After that, new moo durations are generated by applying two functions:

\( f_1(x)=\left\lfloor \frac{a_1\,x}{d_1} \right\rfloor+b_1 \) and \( f_2(x)=\left\lfloor \frac{a_2\,x}{d_2} \right\rfloor+b_2 \).

Starting from the initial duration c, the cows generate more moo times by applying these functions repeatedly: for every moo time in the sequence, its two new moo times \( f_1(\cdot) \) and \( f_2(\cdot) \) are computed. Duplicate durations are discarded and all moo durations are kept in a sorted list. The cows moo exactly N times and your task is to determine the length of the N-th moo.

The constants satisfy:

• \(1 \leq d_1 < a_1 \leq 20\), \(0 \leq b_1 \leq 20\).
• \(1 \leq d_2 < a_2 \leq 20\), \(0 \leq b_2 \leq 20\).

No moo time will be greater than or equal to \(2^{63}\).

For example, consider the following input:

3 10
4 3 3 17 8 2

The process is as follows:

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

The 10th moo time is 65.

Note: Partial feedback will be provided on the first 50 submissions.

inputFormat

The input consists of two lines.

The first line contains two integers: c (the initial moo duration) and N (the total number of moos, with 1 < N < 4,000,000).

The second line contains six integers: a1, b1, d1, a2, b2, and d2, which represent the constants for the functions \( f_1(x)=\left\lfloor \frac{a_1 x}{d_1} \right\rfloor+b_1 \) and \( f_2(x)=\left\lfloor \frac{a_2 x}{d_2} \right\rfloor+b_2 \).

outputFormat

Output a single integer: the length of the N-th moo.

sample

3 10
4 3 3 17 8 2

65