Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
ans = 0
M = 60
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while a:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
    while c < M:
        anslist[c] += counter[-c-1]
        c += 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A = list(map(int,input().split()))
count = 0
now = 1
city = [1]
while count < K:
    count +=  1
    now = A[now-1]
    if now in city:
        break
    else:
        city.append(now)
if count == K:
    print(now)
else:
    n = city.index(now)
    K -= n
    count -= n
    K %= count
    print(city[n+K])

### FIXED CODE ###

N,K=map(int,input().split())
A = list(map(int,input().split()))
count = 0
now = 1
city = [1]
city2 = {1}
while count < K:
    count +=  1
    now = A[now-1]
    if now in city2:
        break
    else:
        city.append(now)
        city2.add(now)
if count == K:
    print(now)
else:
    n = city.index(now)
    K -= n
    count -= n
    K %= count
    print(city[n+K])
### BUGGY CODE ###

N, K= map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 10] * N
for i in range(N):
  if i == 0:
    DP[i] = 0
  elif i == 1:
    DP[i] = DP[i-1] + abs(H[i] - H[i - 1])
  else:
    for j in range(1, K + 1):
      if i - j >= 0:
        DP[i] = min(DP[i], DP[i - j] + abs(H[i] - H[i - j]))

#print(DP)
print(DP[-1])


### FIXED CODE ###

N, K= map(int, input().split())
H = list(map(int, input().split()))

DP = [10 ** 10] * N
DP[0] = 0
DP[1] = abs(H[1] - H[0])
for i in range(2, N):
  for j in range(1, K + 1):
    if i - j >= 0:
      DP[i] = min(DP[i], DP[i - j] + abs(H[i] - H[i - j]))

#print(DP)
print(DP[-1])
### BUGGY CODE ###

N = int(input())
R = [int(input()) for i in range(N)]

sa = R[N - 1] - R[N - 2]
for i in reversed(range(N)):
    for j in reversed(range(i)):
        tmp = R[i] - R[j]
        if tmp > sa:
            sa = tmp
print(sa)


### FIXED CODE ###

N = int(input())

min_v = int(input())
r = int(input())
max_v = r - min_v
if min_v > r:
    min_v = r

for _n in range(2, N):
    r = int(input())
    if max_v < r - min_v:
        max_v = r - min_v
    if min_v > r:
        min_v = r
print(max_v)
### BUGGY CODE ###

k=int(input())
ans=1
s=7%k
if k%2==1:
    while True:
        if s==0:
            break
        else:
            s=s*10+7
            s%=k
            ans+=1
    print(ans)
else:
    print(-1)

### FIXED CODE ###

k=int(input())
ans=1
judge=0
s=7%k
while ans<=k:
    if s==0:
        judge=1
        break
    else:
        s=s*10+7
        s%=k
        ans+=1
if judge==1:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a = input()
l = a.split()
for i in range(0,n):
    l[i] = int(l[i])
dp = []
for i in range(0,n+1):
    dp.append(0)
dp[0] = 1
for i in range(1,n):
    if min(l[:i+1])+1 >l[i]:
        dp[i] = dp[i-1]+1
    else:
        dp[i]=dp[i-1]
print(dp[n-1])

### FIXED CODE ###

n = int(input())
a = input()
l = a.split()
for i in range(0,n):
    l[i] = int(l[i])
dp = []
dp = [1]
for i in range(0,n+1):
    dp.append(0)
m = l[0]
for i in range(1,n):
    if l[i] < m:
        m = l[i]

    if m+1 >l[i]:
        dp[i] = dp[i-1]+1
    else:
        dp[i]=dp[i-1]
print(dp[n-1])
### BUGGY CODE ###

from collections import defaultdict
from functools import reduce
import heapq as hq

MOD = 10**9+7
N,M = map(int,input().split())
S,T = map(int,input().split())
S,T = S-1,T-1

E = defaultdict(list)

for _ in range(M):
  u,v,d = map(int,input().split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))

dist = [None]*N
flag = [None]*N

Q = [(0,S,False),(0,T,True)]

D = float('inf')

while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break
  if flag[v] is None:
    flag[v] = f
    dist[v] = d
    for u,dd in E[v]:
      if flag[u] != f:
        hq.heappush(Q,(d+dd,u,f))

  elif flag[v] != f:
    D = min(dist[v]+d,D)

del Q


cnts = [0]*N
cnts[S] = 1
cnts[T] = 1

for d,v in sorted((d,v) for v,d in enumerate(dist) if d is not None):
  f = flag[v]
  c = cnts[v]
  for u,dd in E[v]:
    if f == flag[u] and d+dd == dist[u]:
      cnts[u] = (cnts[u]+c)%MOD

def it():
  for v in range(N):
    for u,d in E[v]:
      if flag[v] == True and flag[u] == False and dist[v]+d+dist[u] == D:
        yield cnts[u]*cnts[v] % MOD
X = list(it())

total = reduce(lambda a,b:(a+b)%MOD, X)
total = total*total % MOD

sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X))

print((total-sub)%MOD)

### FIXED CODE ###

from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = map(int,stdin.readline().split())
S,T = map(int,stdin.readline().split())
S,T = S-1,T-1
 
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
  u,v,d = map(int,line.split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [None]*N
dT = [None]*N
 
Q = [(0,S,False),(0,T,True)]
 
D = float('inf')
 
 
while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break

  dM = dT if f else dS
  dN = dS if f else dT
  if dM[v] is None:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] is None and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
 
  if dN[v] is not None:
    D = min(dN[v]+d,D)
 
del Q

def helper(start,dist):
  cnts = [0]*N
  cnts[start] = 1

  for d,v in sorted((d,v) for v,d in enumerate(dist) if d is not None):
    c = cnts[v]
    for u,dd in E[v]:
      if dd+d == dist[u]:
        cnts[u] = (cnts[u]+c) % MOD

  return cnts

Sn = helper(S,dS)
Tn = helper(T,dT)


def it():
  for v in range(N):
    if dS[v] is not None:
      ds = dS[v]
      if dT[v] == ds and ds*2 == D:
        yield Sn[v]*Tn[v] % MOD
      else:
        for u,d in E[v]:
          if dT[u] is not None and abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = list(it())

 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X),0)
print((total-sub)%MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a, b):
    # print(gcd(a,b))
    return a * b//gcd(a, b)

mk = 1
for i in a:
    mk = lcm(mk, i)

k = 0
for j in a:
    k = (k +  mk // j) %MOD
print(k %MOD)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

mk = 1
for i in a:
    mk = mk * i//gcd(mk, i)

k = 0
for j in a:
    k +=  mk // j
print(k %MOD)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
for i in range(1, N+1):
    print(a.index(i) + 1, end=" ")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
rev = [0]*N
for i in range(N):
    rev[a[i] - 1] = i +1
for i in range(N):
    print(rev[i], end=" ")
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
Sum=[0]
sum=0
for i in range(1,n+1):
  sum=s[:i].count("AC")
  Sum.append(sum)
for i in range(q):
  l,r=map(int,input().split())
  print(Sum[r]-Sum[l])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
Sum=[0]
sum=0
stack="Q"
for i in range(n):
  if stack=="A" and s[i]=="C":
    sum+=1
  stack=s[i]
  Sum.append(sum)
for i in range(q):
  l,r=map(int,input().split())
  print(Sum[r]-Sum[l])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

a = []
for i in range(10):
    a.append(str(i))
    
ans = 0    
s = 0
for i in a:
    for j in a:
        for k in a:
            for l in range(N):
                if S[l] == i and s == 0:
                    s = 1
                elif S[l] == j and s == 1:
                    s = 2
                elif S[l] == k and s == 2:
                    ans += 1
                    break
            s = 0
            
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

a = []
for i in range(10):
    a.append(str(i))
    
ans = 0    
s = 0
for i in a:
    for j in a:
        for k in a:
            for l in range(N):
                if S[l] == i and s == 0:
                    s = 1
                elif S[l] == j and s == 1:
                    s = 2
                elif S[l] == k and s == 2:
                    ans += 1
                    break
            s = 0
            
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())
S = str(input())
mod = 10**9+7
lens = len(S)
length = lens+K

L = 1
pow_dic = {}
pow_dic[0] = 1
for i in range(1, 10**6*2+1):
    L = L*i%mod
    pow_dic[i] = L
ans = 0
for rest in range(K+1):
    lenall = length-rest-1
    nlens = lens-1
    l = pow_dic[lenall]*pow(pow_dic[lenall-nlens], mod-2, mod)%mod
    r = pow_dic[nlens]
    comb = l*pow(r, mod-2, mod)%mod
    ans += pow(25, K-rest, mod)*pow(26, rest, mod)*comb%mod
    ans %= mod
print(ans%mod)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())
S = str(input())
mod = 10**9+7
lens = len(S)
length = lens+K

L = 1
pow_dic = [0]*(10**6*2+1)
pow_dic[0] = 1
for i in range(1, 10**6*2+1):
    L = L*i%mod
    pow_dic[i] = L%mod
ans = 0
for rest in range(K+1):
    lenall = length-rest-1
    nlens = lens-1
    l = pow_dic[lenall]*pow(pow_dic[lenall-nlens], mod-2, mod)%mod
    r = pow_dic[nlens]
    comb = l*pow(r, mod-2, mod)%mod
    ans += pow(25, K-rest, mod)*pow(26, rest, mod)*comb%mod
    ans %= mod
print(ans%mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.deepcopy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
            last_spl=i-1
        nxt_cnt=[0]*num_sp

    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

    spl_l=[]
    for aaa in range(h):
        spl_l.append(sum(tmp[:aaa]))
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = spl_l[j]
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
for n in range(N):
    path = [0]+A[0:n]+A[n+1:]+[0]
    print(sum(abs(path[i]-path[i-1]) for i, _ in enumerate(path)))

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
A = [0]+[int(_) for _ in stdin.readline().rstrip().split()]+[0]
S = sum(abs(A[i+1]-A[i]) for i in range(N+1))
for i in range(1,N+1):
    print(S-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
b=[]
count=0
count_1=0

for i in range(M):
    if ps[i][1]=="AC" and ps[i][0] not in a:
        a.append(ps[i][0])

for j in range(M):
    if ps[j][0] not in a:
        pass
    elif ps[j][0] not in b:
        if ps[j][0] in a and ps[j][1]=="WA":
            count+=1
        elif ps[j][0] in a and ps[j][1]=="AC":
            b.append(ps[j][0])

print(len(a),count)


### FIXED CODE ###

N,M=map(int,input().split())

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
corrects = []
wrongs = {}
for m in range(M):
  p, s = input().split()
  if p not in corrects:
    if s == "WA":
      if p not in wrongs:
        wrongs[p] = 0        
      wrongs[p] += 1
    elif s == "AC":
      corrects.append(p)
  
total_wrongs = 0
for p in corrects:
  if p in wrongs:
	  total_wrongs += wrongs[p]
      
print(len(corrects), total_wrongs)

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
corrects = [0 for _ in range(N)]
wrongs = [0 for _ in range(N)]
for m in range(M):
  p, s = input().split()
  p = int(p)
  if corrects[p-1] == 0:
    if s == "WA":
      wrongs[p-1] += 1
    elif s == "AC":
      corrects[p-1] = 1
      corrects.append(p)
  
total_wrongs = 0
total_correct = 0
for i in range(N):
  if corrects[i] > 0:
      total_wrongs += wrongs[i]
      total_correct += 1
  
print(total_correct, total_wrongs)
### BUGGY CODE ###

# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))


### FIXED CODE ###

# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))
### BUGGY CODE ###

N, W = map(int, input().split())
wvlist = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w >= wvlist[i][0]:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wvlist[i][0]] + wvlist[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
wvlist = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w >= wvlist[i][0]:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wvlist[i][0]] + wvlist[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[N][W])
### BUGGY CODE ###

#int(input())
#map(int,input().split())
#list(map(int,input().split()))
import math
a,b,n=map(int,input().split())
l=[]
for x in range(n+1):
    l.append(math.floor((a*x)/b)-a*math.floor(x/b))
print(max(l))

### FIXED CODE ###

import math
a,b,n=map(int,input().split())
l=[]
if n>=b:
    x=b-1
else:
    x=n
print(math.floor((a*x)/b)-a*math.floor(x/b))
### BUGGY CODE ###

def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        route = [None]
        dfs_stack = [(i, None)]            
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
                
            visited |= {u}
            if u in route:
                return True
            dfs_stack.extend((v, u) for v in g[u])
            
            route.append(u)
    return False

from sys import stdin
from collections import defaultdict
readline = stdin.readline


v, e = map(int, readline().split())
g = defaultdict(set)
for i in range(e):
    s, t = map(int, readline().split())
    g[s] |= {t}
print(1 if is_contain_cycle(g, v) else 0)

### FIXED CODE ###

def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        #route = Stack([None])
        route = [None]
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
            if u in route:
                return True
            if u in visited:
                continue
            visited |= {u}
            dfs_stack.extend((v, u) for v in g[u])
            route.append(u)
    return False

from sys import stdin
from collections import defaultdict


readline = stdin.readline

v, e = map(int, readline().split())
g = defaultdict(set)
for i in range(e):
    s, t = map(int, readline().split())
    g[s] |= {t}
print(1 if is_contain_cycle(g, v) else 0)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]

import sys
import math

a.sort()
f.sort(reverse=True)

def cond(score):
    _max = 0
    count = 0
    for i in range(n):
        if a[i] * f[i] <= score:
            continue
        target = (score // f[i])
        count += a[i] - target
        if count > k:
            return False, -1
        _max = max(_max, target * f[i])
    if count <= k:
        return True, _max

def binary_search(start, end, result):
    middle = math.ceil((start + end) / 2)
    if middle == end:
        if result[start]:
            return start
        else:
            return end
    is_ok, score = cond(middle)
    result[middle] = is_ok
    if is_ok:
        return binary_search(start, min(middle, score), result)
    else:
        return binary_search(middle, end, result)

# 0
if sum(a) <= k:
    print(0)
    sys.exit(0)

max_score = 0
for i in range(n):
    max_score = max(max_score, a[i] * f[i])

# max
if k == 0:
    print(max_score)
    sys.exit(0)

# 1 - max
if cond(1)[0]:
    print(1)
    sys.exit(0)

result = {1: False, max_score: True}
print(binary_search(1, max_score, result))


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]

import sys
import math

a.sort()
f.sort(reverse=True)

def cond(score):
    _max = 0
    count = 0
    for i in range(n):
        if a[i] * f[i] <= score:
            continue
        target = (score // f[i])
        count += a[i] - target
        if count > k:
            return False, -1
        _max = max(_max, target * f[i])
    if count <= k:
        return True, _max

def binary_search(start, end, result):
    middle = math.ceil((start + end) / 2)
    if middle == end:
        if result[start]:
            return start
        else:
            return end
    is_ok, score = cond(middle)
    result[middle] = is_ok
    if is_ok:
        return binary_search(start, min(middle, score), result)
    else:
        return binary_search(middle, end, result)

# 0
if sum(a) <= k:
    print(0)
    sys.exit(0)

max_score = 0
for i in range(n):
    max_score = max(max_score, a[i] * f[i])

# max
if k == 0:
    print(max_score)
    sys.exit(0)

# 1 - max
if cond(1)[0]:
    print(1)
    sys.exit(0)

result = {1: False, max_score: True}
print(binary_search(1, max_score, result))
### BUGGY CODE ###

def main():
  from sys import stdin
  readline = stdin.readline
  h, n = map(int, readline().split())
  l = [list(map(int, readline().split())) for i in range(n)]

  dp = [10 ** 9 for i in range(h+1)]

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]

  print(dp[h])


main()


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    lh = []
    for i, b in enumerate(B):
        heapq.heappush(lh, [-b, i])

    count = 0
    while len(lh) > 0:
        b, i = heapq.heappop(lh)
        a, b = A[i], B[i]
        c = B[i-1]+B[(i+1) % N]
        if b > a and b >= c:
            d, m = divmod(b-a, c)
            if m == 0:
                count += d
                B[i] = a
            if m != 0:
                d, m = divmod(b, c)
                count += d
                B[i] = m
                heapq.heappush(lh, [-B[i], i])
    # print(*A)
    # print(*B)
    for a, b in zip(A, B):
        if a != b:
            print(-1)
            return

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()