题目描述

满月的时候，和狼一样，牛们也在月光下叫。他们从不嚎叫，而是哞叫。

每次哞叫都有一个时长，可能是 $1$ 秒，也可能是 $10^9$ 秒或更久，牛们真的非常能叫。当然，没有牛哞叫时长会超过或等于 $2^63$ 秒。

牛们的哞叫可以找到规律，这并不奇怪。贝茜会选择一个整数 $c$ 来作为初始时长。之后，牛们根据两条公式确定更多的时长。这两条公式是：

$f_1(c)=\frac{a_1\cdot c}{d_1}+b_1$

$f_2(c)=\frac{a_2\cdot c}{d_2}+b_2$。

公式中 $a_1,b_1,d_1,a_2,b_2,d_2$ 均为整数。牛们用这两条公式不断地迭代、计算，算得大量的时长。然后她们将这些时长排序，剔除重复的时长，最后取前 $n$ 个整数为她们 $n$ 次哞叫的时长。请你计算，第 $n$ 次哞叫的时长是多少。

输入格式

• 第 $1$ 行：两个整数：$c,n$。

• 第 $2$ 行：三个整数：$a_1,b_1,d_1$。

• 第 $3$ 行：三个整数：$a_2,b_2,d_2$。

输出格式

• 第 $1$ 行：一个整数，表示第 $n$ 次哞叫的时长。

3 10 
4 3 3 
17 8 2 

65 

数据规模与约定

对于 $100\%$ 的数据，$1 \le c \le 100$，$1 < n < 4\times 10^6$，$1 \le d_1 < a_1 \le 20$，$1 \le d_2 < a_2 \le 20$，$0 \le b_1,b_2 \le 20$。

题目来源

Usaco2009 Mar Gold