보름달 아래 소의 울음

보름달이 뜨면 소들은 사촌 격인 늑대나 코요테처럼 달을 향해 웁니다. 물론 하울링 대신 "음메(moo)" 소리를 냅니다.

각 "음메"는 일정한 시간 동안 지속됩니다. 짧은 울음은 길이가 1일 수도 있고, 긴 울음은 24나 심지어 1000000000 이상일 수도 있습니다(소는 마음만 먹으면 정말 길게 웁니다). 단, 어떤 울음도 길이가 2^63 이상이 되지는 않습니다.

소들의 울음에는 규칙이 있습니다. 먼저 베시(Bessie)가 첫 울음의 길이가 되는 정수 c(1 ≤ c ≤ 100)를 고릅니다.

그다음, 지금까지 나온 각 울음 길이에 아래 두 함수를 적용해 새로운 울음 길이를 만듭니다(나눗셈은 모두 내림 정수 나눗셈입니다).

f1(x) = a1 * x / d1 + b1
f2(x) = a2 * x / d2 + b2

새로 얻은 길이에 다시 두 함수를 적용하는 식으로 계속 진행하며, 지금까지 나온 모든 울음 길이를 오름차순으로 정렬한 하나의 목록으로 관리합니다. 이때 중복된 값은 하나만 남깁니다.

소들은 최대 N번(1 ≤ N ≤ 4000000) 울 수 있습니다. 정렬된 목록에서 앞에서부터 N번째 값, 즉 N번 우는 동안 나온 가장 긴 울음의 길이를 구하세요.

각 상수는 다음 조건을 만족합니다: 1 ≤ d1 < a1 ≤ 20, 0 ≤ b1 ≤ 20, 1 ≤ d2 < a2 ≤ 20, 0 ≤ b2 ≤ 20.

예를 들어 c = 3, N = 10이고 상수가 다음과 같다고 합시다.

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

첫 울음 길이는 c 값인 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

10번째 값은 65이며, 이 입력에 대한 정답이 됩니다.

보름달 아래 소의 울음

문제

입력

출력