题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

3 10
4 3 3
17 8 2

输出样例

65