[Usaco2009 Mar]Moon Mooing 哞哞叫

定义集合 $S$。初始时，$C\in S$。对于 $S$ 中的任意整数 $x$，下列两个整数也属于 $S$：

• $\left\lfloor\dfrac{a_1x}{c_1}\right\rfloor+b_1$；
• $\left\lfloor\dfrac{a_2x}{c_2}\right\rfloor+b_2$。

其中，$\lfloor y\rfloor$ 表示不超过 $y$ 的最大整数，即对 $y$ 向下取整。$S$ 是满足上述条件的最小集合。

将 $S$ 中所有不同的数从小到大排列，并将 $C$ 记为第 $1$ 个数。求该序列中的第 $N$ 个数。

输入格式

第一行包含两个整数 $C$ 和 $N$。

第二行包含三个整数 $a_1,b_1,c_1$。

第三行包含三个整数 $a_2,b_2,c_2$。

输出格式

输出一个整数，表示上述升序去重序列中的第 $N$ 个数。

样例输入

3 10
  4 3 3
  17 8 2

样例输出

65

数据范围

• $1\le C\le 10^9$；
• $1\le N\le 4\times 10^6$；
• 对于 $i=1,2$，有 $1\le c_i\le a_i\le 10^9$，且 $1\le b_i\le 10^9$；
• 题目保证该序列中的第 $N$ 个数存在；
• 题目保证生成前 $N$ 个数时，参考实现进行的所有有符号 $64$ 位整数运算均不会溢出。

来源与许可

本题为 USACO 2009 March 试题「Moon Mooing 哞哞叫」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 10
  4 3 3
  17 8 2

输出

65