题目描述

满月的时候，和狼一样，牛们也在月光下叫，他们从不嚎叫，而是哞叫。 每次哞叫都有一个时长，可能是$\red{1}$秒，可能是$\red{10^9}$秒或更久，牛们真的非常能叫。当然，没有哞叫时长会超过或等于$\red{2^{63}}$ 牛们的哞叫可以找到规律，这并不奇怪，贝茜会选择一个整数$\red{C(1≤}$$\red{C≤}$$\red{100)}$来作为初始时长，之后，牛们根据两条公式确定更多的时长，这两条公式是:

$\red{F1(c) =\frac{a_iC}{c_1}+b_1 }$ $\red{F2(C)=\frac{a_2C}{c_2}+b_2}$

牛们用这两条公式不断地迭代、计算，算得大量的时长，然后她们将这些时长排序，剔除重复的时长，最后取前$\red{N(1 ≤}$$\red{N≤}$$\red{4000000)}$个整数为她们$\red{N}$次哞叫的时长，请你计算，第$\red{N}$次哞叫的时长是多少，公式中的常量均为整数，满足下列关系:$\red{1≤}$$\red{d_1<a_1≤}$$\red{20}$;$\red{0≤}$$\red{b_1≤}$$\red{20}$;$\red{1≤}$$\red{d_2< a_2≤}$ $\red{20}$;$\red{0≤}$ $\red{b_2≤}$ $\red{20.}$

输入格式

第一行两个数，$\red{C}$和$\red{N}$

第二行$\red{3}$个数，$\red{a1,b1,c1 }$第三行$\red{3}$个数，$\red{a2,b2,c2}$

输出格式

一个整数代表最长的那一次嚎叫

样例

输入样例

3 10
4 3 3
17 8 2

输出样例

65