보름달이 되면 늑대와 코요테처럼 소들도 어떤 종류의 마법에 걸린다. 그들은 달을 해야 음매~~~(moo)

모든 음매~ 는 일정한 시간동안 지속한다. 짧은 음매~ 는 시간 1 만큼 지속하고, 긴 음매~ 는 시간 24 혹은 심지어 1,000,000,000 까지 울부짖는다.(소들은 그들이 원하는시간 만큼의 음매~ 소리를 낼 수 있다.) 어떤 음매소리도 2^63 이상 지속되지는 않는다.

소들은 소리는 일정한 패턴을 가지고 있다.

암소 베시는 음매~ 소리의 처음 크기 정수 c (1 <= c <= 100)값을 선택할수 있다. 암소 베시가 크기 c 동안 음매~ 한 후에 소들은 연속한 음매~ 시간을 측정한다. 그들은 각 소리에 대한 두 가지 공식을 적용한다. 더욱 많은 음매~ 시간을 측정하기 위해

두 공식은 다음과 같다.:

• f1(c)=a1*c/d1+b1 (integer divide, of course) and
• f2(c)=a2*c/d2+b2.

그들은 정렬된 리스트를 유지한다. 모든 가능한 음매~ 시간을.(중복된 것은 버린다) 그들은 전체 N 시간 우는 것을 허락한다.(1 <= N <= 4,000,000). 그들이 끝내기전 가장 긴 음매~ 시간의 길이를 구하라.

공식의 상수는 다음의 제한을 가진다.

1 <= d1 < a1; d1 < a1 <= 20; 0 <= b1 <= 20; 1 <= d2 < a2; d2 < a2 <= 20; 0 <= b2 <= 20.

    a1=4    b1=3     d1=3
    a2=17   b2=8     d2=2

처음 음매~ 시간은 3 . 전체 시간은

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

입력

• 첫 줄은 정수 c 와 N
• 다음 줄 세 정수 값 :a1,b1,d1
• 다음 줄 세 정수 값 :a2,b2,d2

출력

입출력 예

입력

3 10
4 3 3
17 8 2

출력

65

출처: USACO 2009 March Gold