Harryxun/stf_run huggingface dataset:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
            KARI = []
            KARI.append(DP[i-1][j])
            if j % Magic[i][0] == 0:
                KARI.append((j//Magic[i][0]) * Magic[i][1])
            r = j // Magic[i][0]
            for k in range(r):
                KARI.append(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1])
            DP[i][j] = min(KARI)
print(min(DP[N-1][H:MAX_A]))

                
            
        


### FIXED CODE ###

H,A = map(int,input().split())
X = int(H // A)
if (H%A)!=0:
    X += 1
print(X)
from math import *
from collections import *
from random import *
from bisect import *
import sys
input=sys.stdin.readline
def lis():
    return list(map(int,input().split()))
def ma():
    return map(int,input().split())
def inp():
    return int(input())
x=inp()
s='No'
if(s>=30):
    s='Yes'
print(s)
            

        
            
        
    
        
    


### FIXED CODE ###

from math import *
from collections import *
from random import *
from bisect import *
import sys
input=sys.stdin.readline
def lis():
    return list(map(int,input().split()))
def ma():
    return map(int,input().split())
def inp():
    return int(input())
x=inp()
s='No'
if(x>=30):
    s='Yes'
print(s)
if (A-B) > C:
  print (0)
else:
  print (A-B)

### FIXED CODE ###

def main():
    A, B, C = [int(_) for _ in input().split()]
    if (A-B) < C:
      print (C-A+B)
    else:
      print(0)
main()
import math

def better_gcd(a,b,c):
    tup = set((a,b,c))
    kinds = len(tup)
    if kinds == 3:
        return math.gcd(a, math.gdc(b, c))
    elif kinds == 2:
        return math.gcd(*tup)
    else:
        return a

K = int(input())
ans = 0
for i in range(1, 1+K):
    for j in range(1, 1+K):
        for k in range(1, 1+K):
            ans += better_gcd(i,j,k)
print(ans)

### FIXED CODE ###

K = int(input())
# K = 2
import math
import itertools

def better_gcd(a,b,c):
    tup = set((a,b,c))
    kinds = len(tup)
    if kinds == 3:
        return math.gcd(a, math.gcd(b, c)) * 6
    elif kinds == 2:
        return math.gcd(*tup) * 3
    else:
        return a

ans = 0
cands = list(itertools.combinations_with_replacement(range(1,K+1), 3))
for c in cands:
    ans += better_gcd(*c)
print(ans)
S = input()
T = input()

naga = len(S)
count = 0
for i in range(naga):
    ss = S[i]
    tt = T[i]
    if S.find(ss) != -1 :
        count = count + 1
    S = S.replace(ss,"!")
    S = S.replace(tt,ss)
    S = S.replace("!",tt)

    if count > 28:
        break


if S == T:
    print("Yes")
else:
    print("No")


### FIXED CODE ###


A, B, C = (int(i) for i in input().split())

if max(A,B,C) == A:
    print(A*10+B+C)
elif max(A,B,C) == B:
    print(B*10+A+C)
elif max(A,B,C) == C:
    print(C*10+B+A)
cur = input()
if cur == "Sunny":
  print("Cloudy")
else if cur == "Rainy":
  print("Sunny")
else:
  print("Rainy")

### FIXED CODE ###

l = ["Sunny", "Cloudy", "Rainy", 'Sunny']
print(l[l.index(input()) + 1])
n, k = map(int, input().split())
s = input()

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k-1]
      b -= off[i-1]
    s = a+b
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)


### FIXED CODE ###

n, k = map(int, input().split())
s = input()

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k-1 <= len(off)-1:
        b += off[i+k-1]
      b -= off[i-2]
    s = a+b
    # print (a,b)
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)
from statistics import mode
n = int(input())
a = list(map(int,input().split()))
b = []
c = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
if sum(b) != 0:
    cnt = 1
    for num in a:
        st = 0
        st = abs(num - (mode(b) + cnt))
        c.append(st)
        cnt += 1
    print(sum(c))
else:
    print(sum(b))

### FIXED CODE ###

import numpy as np

n = int(input())
a = list(map(int,input().split()))
b = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
test = [int(np.mean(b))-1,int(np.mean(b)),int(np.mean(b))+1,int(np.median(b))]
test = list(set(test))
ans = []
s = 9999999999999
for i in test:
    cnt = 1
    c = []
    for num in a:
        st = 0
        st = abs(num - (i+cnt))
        c.append(st)
        cnt += 1
    ans.append(np.sum(c))
print(np.min(ans))
import math
MOD = 10**9 + 7
X, Y = [int(x) for x in input().split()]
if (X+Y) % 3 != 0:
    print(0)
    exit()
r = (X+Y) // 3
k = X - r
fact = [1] * (r+2)
print(math.factorial(r)//(math.factorial(r-k)*math.factorial(k)) %MOD)


### FIXED CODE ###

import numpy as np
def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
MOD = 10**9 + 7
fact, invfact = make_fact(U,MOD)

X, Y = [int(x) for x in input().split()]
if (X+Y) % 3 != 0:
    print(0)
    exit()
r = (X+Y) // 3
k = X - r
if (k < 0 or Y - r < 0):
    print(0)
else:
    print(fact[r] * invfact[r-k] % MOD * invfact[k] % MOD)
S = input()
S = S[::-1]
#print(S)

def memoize(f):
	table = {}
	def func(*args):
		if not args in table:
			table[args] = f(*args)
		return table[args]
	return func

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@memoize
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res

total = search(0,0)
print(total%(10**9+7))


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
# 158 B

n, a , b = map(int, input().split())
s = ""

while len(s) < n:
    s += a * "b"
    if len(s) >= n:
        break
    s += b * "r"
    if len(s) >= n:
        break

s = s[:n]
print(s.count("b"))


### FIXED CODE ###

n, a, b = map(int, input().split())
num = 0

x = n // (a + b)
num += (x * a)

y = n % (a + b)

if y <= a:
    num += y
else:
    num += a

print(num)
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int X = scan.nextInt();
		int N = scan.nextInt();
		Integer p[] = new Integer[N];
		//int min = Math.abs(100 - X);
		int min = 100;
        int result = X;

		for (int i = 0; i < N; i++) {
			p[i] = scan.nextInt();
		}

		for (int i = 0; i <= 200; i++) {
			if (Math.abs(X - i) < min && !Arrays.asList(p).contains(i)) {
				min = Math.abs(X - i);
				result = i;
			}
		}

		System.out.println(result);

	}

}

### FIXED CODE ###

X, N = map(int, input().split(' '))
P = []
if N > 0:
  P = sorted(list(map(int, input().split(' '))))
  ans = 0
  i = 0
  while True:
    if (X-i) not in P:
      ans = (X-i)
      break
    elif (X+i) not in P:
      ans = (X+i)
      break
    else:
      i += 1

if N > 0:
  print(ans)
else:
  print(X)
N = int(input())
plan = [0] + list(map(int, input().split())) for i in range(N)
f = True
for i in range(N):
    time = plan[i+1][0]-plan[i][0]
    dist = abs(plan[i+1][1]-plan[i][1])+abs(plan[i+1][2]-plan[i][2])
    if dist>time or dist%2 != time%2:
        f = False    
print('Yes' if f else 'No')

### FIXED CODE ###

N = int(input())
t,x,y = 0,0,0
f = True
for i in range(N):
    ti,xi,yi = map(int, input().split())
    p=ti-t
    d=abs(xi-x)+abs(yi-y)
    if p<d or p%2 != d%2:
        f = False
        break 
    t,x,y = ti,xi,yi
print('Yes' if f else 'No')
def main() :
    n = int(input())
    nums = [int(i) for i in input().split()]
    exchange_count = 0

    for i in range(n) :
        minj = i
        for j in range(i,n) :
            if nums[j] < nums[minj] :
                minj = j
            if minj != i :
                exchange_count += 1
        nums[i], nums[minj] = nums[minj], nums[i]

        print(" ".join(map(str, nums)))
        print(excnage_count)

if __name__ == '__main__' :
    main()

### FIXED CODE ###

def main() :
    n = int(input())
    nums = [int(i) for i in input().split()]
    exchange_count = 0

    for i in range(n) :
        minj = i
        for j in range(i, n) :
            if nums[j] < nums[minj] :
                minj = j
        if minj != i :
                exchange_count += 1
        nums[i], nums[minj] = nums[minj], nums[i]

    print(" ".join(map(str, nums)))
    print(exchange_count)

if __name__ == '__main__' :
    main()
n,a,b=map(int,input().split())
w='z'*a+'x'*b
f=''
for i in range(1000):
    f+=w
    d=f[:n]
print(d.count('z'))

### FIXED CODE ###

s=input()
if s =='AAA' or s=='BBB':
    print('No')
else:
    print('Yes')
import numpy as np
n,k = map(int,input().split())

a = [0 for _ in range(n)]

a = [int(s) for s in input().split()]

a_sum = [0 for _ in range(n+1)]
a_sum[0] = 1


a_sum[1:] = np.cumprod(a)
#print(a_sum)

score = [0 for _ in range(n-k+1)]

for i in range(k,n+1):
    score[i-k] = int(a_sum[i]/a_sum[i-k])

#print(score)

for i in range(1,n-k+1):
    if(score[i] > score[i-1]):
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

n,k = map(int,input().split())

a = [0 for _ in range(n)]

a = [int(s) for s in input().split()]

for i in range(k,n):
    if(a[i] > a[i-k]):
        print("Yes")
    else:
        print("No")
import numpy as np

N, K = map(int, input().split())
p = (np.array(list((map(int, input().split())))) + 1) / 2

ans = 0

for num in range(len(p)):
    tmp = p[num:num+K].sum()
    if ans < tmp:
        ans = tmp

print(ans)

### FIXED CODE ###

# numpy使うときは、PyPyは不可
import numpy as np

N, K = map(int, input().split())
P = (np.array(list((map(int, input().split())))) + 1)

"""
ans = 0

for num in range(len(p)):
    tmp = p[num:num+K].sum()
    if ans < tmp:
        ans = tmp

print(float(ans))

"""

# 回答
Pcum = np.zeros(N + 1, np.int32)
Pcum[1:] = P.cumsum()

length_K_sums = Pcum[K:] - Pcum[0:-K]
print(length_K_sums.max() / 2)
def root(x):
  if r[x] < 0:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, x in enumerate(road):
  x1_me = x[0]
  x2_me= x[1]
  x1 = root(x1_me)
  x2 = root(x2_me)
  #print("x1", x1, "x2", x2)
  
  if r[x1] == -1 and r[x2] == -1:
    r[x2] = x1
  elif r[x1] == -1 or r[x2] == -1:
    if r[x1] > r[x2]:
      r[x2] = r[x1]
    else:
      r[x1] = r[x2]
  else:
    if r[x1] > r[x2]:
      r[x1] = r[x2]
    else:
      r[x2] = r[x1]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノードxが属するメンバーをリスト形式で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
    #親全てをリスト形式で返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
    #グループ数の合計を返す
        return len(self.roots())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-1)
N=list(str(input()))
ans=0
for i in range(1,len(N)):
    if N[i]!='9':
        ans+=int(N[0])-1
        ans+=(len(N)-1)*9
        print(ans)
        exit()
for i in range(N):
    ans+=int(N[i])
print(ans)
        

### FIXED CODE ###

N=list(str(input()))
ans=0
if len(N)==1:
    print(int(N[0]))
    exit()
for i in range(1,len(N)):
    if N[i]!='9':
        ans+=int(N[0])-1
        ans+=(len(N)-1)*9
        print(ans)
        exit()
for i in range(len(N)):
    ans+=int(N[i])
print(ans)
import fractions
n,m = map(int,input().split())
a,b = map(int,input().split())
lcm = (a * b) // fractions.gcd(a, b)
x = m // (int(lcm)/2)
y = m // lcm
print(int(x-y))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def div_ceil(x, y): return (x + y - 1) // y
 
N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = A[0]
for a in A[1:]:
    L *= a // gcd(L, a)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)
N,K = map(int,input().split())
S = list(input())
if S[K] == "A":
  S[K] = "a"
  STR = "".join(S)
  print(STR)
elif S[K] == "B":
  S[K] = "b"
  STR = "".join(S)
  print(STR)
else:
  S[K] = "c"
  STR = "".join(S)
  print(STR)

### FIXED CODE ###

N,K = map(int,input().split())
S = list(input())
if S[K-1] == "A":
  S[K-1] = "a"
  STR = "".join(S)
  print(STR)
elif S[K-1] == "B":
  S[K-1] = "b"
  STR = "".join(S)
  print(STR)
else:
  S[K-1] = "c"
  STR = "".join(S)
  print(STR)
N, L = map(int,input().split(' '))
l=list(range(L,N+L,1))
minabs = min([abs(x) for x in l])
if N+L+1<=0:
    print(sum(l)+minabs)
else:
    print(sum(l)-minabs) 

### FIXED CODE ###

inp = str(input())
def a(inp):
    for x in range(3):
    
        if inp[x]==inp[x+1]:
            return 'Bad'
    return 'Good'
print(a(inp))
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count+1):
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)
# -*- coding: utf-8 -*-
a=[]
ans="Yay!"
for _ in range(6):
  a.append(int(input()))
for i in range(5):
  for j in range(i+1,5):
    if abs(a(i)-a(j))>a(5):
      ans=":("
      break
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a=[]
ans="Yay!"
for _ in range(6):
  a.append(int(input()))
for i in range(5):
  for j in range(i+1,5):
    if abs(a[i]-a[j])>a[5]:
      ans=":("
      break
print(ans)
import math

n = int(input())
t = []
for _ in range(n):
    t.append(int(input()))

ans = t[0]
for ti in t:
    ans = ans * ti // math.gcd(ans, ti)


print(ans)


### FIXED CODE ###

import fractions

n = int(input())
t = []
for _ in range(n):
    t.append(int(input()))

ans = t[0]
for ti in t:
    ans = ans * ti // fractions.gcd(ans, ti)


print(ans)
K, S = map(int,input().split())
listK = [i for i in range(K+1)]
list2K = [i for i in range(K**2)]
ans = 0
for i in range(K+1):
    id = bisect.bisect_left(list2K,S-i)
    if id < len(list2K) and list2K[id] == S-i:
        for j in range(K+1):
            id2 = bisect.bisect_left(listK,list2K[id]-j)
            if id2 < len(listK) and listK[id2] == list2K[id]-j:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0 <= z and z <= K:
            ans += 1
print(ans)
n,x,m = map(int,input().split())

li = [-1] * m
v = [False] * m
v2 = [False] * m
v[x+1] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = i ** 2 % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li[:cnt]

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1] + loop_li[0])
else:
    n -= len(ans_li)
    if n % len(loop_li) == 0:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
    else:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])


### FIXED CODE ###

n,x,m = map(int,input().split())

if x == 0:
    print(0)
    exit()

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = (i ** 2) % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1])
else:
    n -= len(ans_li)
    if len(loop_li) == 0:
        print(ans_li[-1])
    else:
        if n % len(loop_li) == 0:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
        else:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
x=int(input())
l=make_divisors(x)
if x==0:
  answer=[0,0]
for i in range(math.ceil(pow(x,0.2))):
  for j in l:
    if pow(i,5)-pow(i-j,5)==x:
      answer=[i,i-j]
      break
print(answer[0],answer[1])

### FIXED CODE ###

import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
x=int(input())
l=make_divisors(x)
if x==0:
  answer=[0,0]
for i in range(math.ceil(2*pow(x,0.2))):
  for j in l:
    if pow(i,5)-pow(i-j,5)==x:
      answer=[i,i-j]
      break
print(answer[0],answer[1])
import sys
n,q=map(int, input().split())
queue = list(map(lambda x: x.strip().split(),sys.stdin.readlines()))
i = 0
while len(queue) > 0:
    if queue[i%len(queue)][1]-=q < 0:
        print("{} {}".format(q[i%len(queue)][0], i*q + q + q[i%len(queue)][1]))
        q.pop(i%len(queue))
    i+=1
  



### FIXED CODE ###

import sys
n, q = map(int, input().split())
queue = [[label, int(num)] for label, num in map(lambda line: line.strip().split(), sys.stdin.readlines())] 
i = 0
time = 0
while len(queue) > 0:
    i = i % len(queue)
    time += q
    queue[i][1] -= q
    if queue[i][1] <= 0:
        time += queue[i][1]
        print("{} {}".format(queue[i][0], time))
        queue.pop(i)
        i -= 1
    i += 1
N,A,B = map(int,input().split())

Blue='b'*A
Red='r'*B
BlueRed=Blue+Red
ans = ''
time = (N // 7)+1
ans= BlueRed*time
ans2=ans[:N]
print(ans2.count('b'))

### FIXED CODE ###

N,A,B = map(int,input().split())

ans = N // (A+B) * A
rem = N % (A+B)
ans += min(rem,A)

print(ans)