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

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
    if t[-2]!=a[1]:
        ans=0
for i in range(n):
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans*=min(t[i+1],a[i+1])%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans=(ans*(min(t[i+1],a[i+1])))%(10**9+7)
print(ans)
### BUGGY CODE ###

def main():
  import collections
  s = input()
  r = []
  x = 0
  for i in range(len(s)):
    x += int(s[-i-1])*10**i
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

### FIXED CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - i - j <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = list()
R = list()

def kitai(p):
  return (p+1)/2

for i in range(N):
  Q.append(kitai(P[i]))

for i in range(N - K + 1):
  if i == 0:
    R.append(sum(Q[i:i+K]))
  else:
    R.append(sum(Q[:i+K])-sum(Q[:i]))

print(max(R))

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = list()
R = [0]
result = 0

for i in P:
  Q.append((i+1)/2)

for i in range(N):
  R.append(R[i] + Q[i])

for i in range(N - K + 1):
  result = max(result,R[i+K]-R[i])

print(result)
### BUGGY CODE ###

import heapq

H,W=map(int, input().split())
DINF = 100000
d = [ [ DINF for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [ [] for _ in range(W+2)] for _ in range(H+2)]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y-1][x] == '.'):  G[y][x].append([y-1,x])
        if (S[y][x-1] == '.'):  G[y][x].append([y,x-1])
        if (S[y+1][x] == '.'):  G[y][x].append([y+1,x])
        if (S[y][x+1] == '.'):  G[y][x].append([y,x+1])

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            q = []
            heapq.heappush(q, [0,y,x])
            while len(q) != 0:
                v = heapq.heappop(q)
                n = v[0]
                iy = v[1]
                ix = v[2]
                d[iy][ix] = n;
                for nv in G[iy][ix]:
                    if d[nv[0]][nv[1]] <= n+1 :
                        continue
                    heapq.heappush(q, [n+1, nv[0], nv[1] ] )
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != DINF:
                        dmax = max(dmax, d[iy][ix])
                    d[iy][ix] = DINF
print(dmax)


### FIXED CODE ###

from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)
### BUGGY CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort()
q.sort()
p.reverse()
q.reverse()

a=p[:]
a.extend(q)
a.extend(r)
a.sort()
a.reverse()
red=0
green=0
sum=0
d=0
for i in range(X+Y):
  if(a[i] in p):
    red+=1
  elif(a[i] in q):
    green+=1
  d+=a[i]
  if(red>X):
    break
  elif(green>Y):
    break
    
if(red<=X and green<=Y):
  print(d)
elif(red>X):
  b=q[:]
  b.extend(r)
  b.sort()
  b.reverse()
  for i in range(max(X,Y)):
    if(i<X):
      sum+=p[i]
    if(i<Y):
      sum+=b[i]
  print(sum)
elif(green>Y):
  b=p[:]
  b.extend(r)
  b.sort()
  b.reverse()
  for i in range(max(X,Y)):
    if(i<X):
      sum+=b[i]
    if(i<Y):
      sum+=q[i]
  print(sum)

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort()
q.sort()
p.reverse()
q.reverse()
p=p[:X]
q=q[:Y]
 
a=p[:]
a.extend(q)
a.extend(r)
a.sort()
a.reverse()
sum=0
for i in range(X+Y):
  sum+=a[i]
print(sum)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
P=[K]*N
for i in range(Q):
    for j in range(N):
        if j==A[i]-1:
            continue
        else:
            P[j]-=1
for k in range(N):
    if P[k]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import heapq
# import time

n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
path = [[] for i in range(n+1)]

for i in range(m):
    # a[i], b[i] = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    path[a].append(b)
    path[b].append(a)
# start = time.time()
# 部屋1から出発して、
ans = [0]*(n+1)
visited = [1]
que = deque([[1, 1]])  # 今の場所、前の場所
que_items = [1]
now = 1
prev = 1
# BFS
while len(que) > 0:
    now, prev = que.popleft()
    # print('pop', now)
    for can_go in path[now]:
        if(not (can_go in visited or can_go in que_items)):
            # print('push', can_go)
            que.append([can_go, now])
            que_items.append(can_go)
    if (now in visited):
        continue
    ans[now] = prev
    visited.append(now)

if (len(visited) != n):
    print('No')
else:
    print('Yes')
    for _ans in ans[2:]:
        print(_ans)

# print(time.time() - start)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import heapq
# import time

n, m = list(map(int, input().split()))
a = [0] * m
b = [0] * m
path = [[] for i in range(n+1)]

for i in range(m):
    # a[i], b[i] = list(map(int, input().split()))
    a, b = list(map(int, input().split()))
    path[a].append(b)
    path[b].append(a)
# start = time.time()
# 部屋1から出発して、
ans = [0]*(n+1)
visited = []
que = deque([[1, 1]])  # 今の場所、前の場所
que_items = set([1])

# BFS
while len(que) > 0:
    now, prev = que.popleft()
    # print('pop', now)
    for can_go in path[now]:
        if(not (can_go in que_items)):  # ここが遅い
            # print('push', can_go)
            que.append([can_go, now])
            que_items.add(can_go)
    ans[now] = prev
    visited.append(now)
    # print(visited)

if (len(visited) != n):
    print('No')
else:
    print('Yes')
    for _ans in ans[2:]:
        print(_ans)

# print(time.time() - start)
### BUGGY CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1,n):
        target_ind = j
        target_h = a_ls[target_ind]
        diff = abs(target_ind - i)
        Sum = target_h + a_ls[i]
        if diff == Sum:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a_ls = list(map(int, input().split()))
L_dict = defaultdict(int)
for i in range(n):
    Li = a_ls[i] + i + 1
    L_dict[Li] += 1

ans = 0
for j in range(n):
    Rj = j + 1 - a_ls[j]
    ans += L_dict[Rj]
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for j in range(1,10000):
    for k in range(1,10000):
        if N > j ** k:
            if ans < j ** k:
                ans = j ** k
 
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for j in range(1,N):
    for k in range(2,100):
        if N >= j ** k:
            if ans < j ** k:
                ans = j ** k
 
if N == 1:
    print(1)
else:
    print(ans)
### BUGGY CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)%2

    ANS+=str(count%2)

print(int(ANS[::-1],2))


### FIXED CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

a,b,x=MAP()

def f(n):
    return (a*n)//b-a*(n//b)

ans=0
pre=0
for i in range(1,x+1):
    pre=f(i)
    #print(ans,pre)
    if ans<f(i):
        ans=pre

print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

a,b,x=MAP()

def f(n):
    return (a*n)//b-a*(n//b)

if b<=x:
    print(f(b-1))
else:
    print(f(x))
### BUGGY CODE ###

from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    raw_number = list(map(int, input().split()))
    numbers = defaultdict(int)

    for num in raw_number:
        numbers[num] += 1

    Q = int(input())

    for _ in range(Q):
        a, b = list(map(int, input().split()))
        numbers[b] += numbers[a]
        numbers[a] = 0
        print(sum([v*k for (k, v) in numbers.items()]))
    
main()

### FIXED CODE ###

class Counter(dict):
    def __missing__(self, i):
        return 0

n = int(input())
a = list(map(int, input().split()))
q = int(input())

total = sum(a)

bucket = Counter()

for item in a:
    bucket[item] += 1

for i in range(q):
    b, c = map(int, input().split())
    taken = bucket[b]
    total -= bucket[b]*b
    bucket[c] += bucket[b]
    bucket[b] = 0
    total += taken*c
    print(total)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

def popcount(n, nc):
    if n == 0:
        return 0
    return 1 + popcount(n % nc, bin(n % nc).count("1"))

def main():
    N = int(input())
    X = input().strip()

    x = int(X, 2)
    xc = X.count("1")
    for i in range(N):
        if X[i] == '0':
            print(popcount(x + (2 ** (N - i - 1)), xc + 1))
        else:
            print(popcount(x - (2 ** (N - i - 1)), xc - 1))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = (int(d) * MODS[i % 6]) % 13
            cur[m:m+13] = priv[0:13]
            cur[0:13] += cur[13:26]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)


### FIXED CODE ###


P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        # print(cur)
        for j in range(13):
            priv[j] = cur[j] % P_MOD
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)
### BUGGY CODE ###

from sys import stdin
import numpy as np
import math

N, Q = map(int,input().split())
S = str(input())
A = [list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)




### FIXED CODE ###

import numpy as np

N, Q = map(int,input().split())
S = str(input())
A = [list(map(int,input().split())) for i in range(Q)]

"""
import random
base_list = ['A', 'T', 'C', 'G']
S = ''
N = int(1e5)
Q = 1
A = [[100, 900]]
for i in range(N):
  S += random.choice(base_list)
"""

L_cnt = np.zeros(N-1)
R_cnt = np.zeros(N-1)

for i in range(N-2):
  L_cnt[i+1] = (S[i:i+2] == 'AC')
  R_cnt[i+1] = (S[N-2-i:N-i] == 'AC')

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
L_cumsum = np.array(L_cnt).cumsum()
R_cumsum = np.array(R_cnt).cumsum()
for i in range(Q):
  ans = n_whole - (L_cumsum[A[i][0]-1] + R_cumsum[N-A[i][1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""
### BUGGY CODE ###

import collections
s = [int(c) for c in input()]
count = 0
prev = {}
for num in s:
    dp = collections.defaultdict(int)
    dp[num] += 1
    for k,v in prev.items():
        i = (k * 10 + num) % 2019
        dp[i] += v
    count += dp[0]
    prev = dp
print(count)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

import collections
s = [int(c) for c in input()]
tmp = 1
mod = 0
count = collections.defaultdict(int)
for i,num in enumerate(s[::-1]):
    mod = (tmp * num + mod) % 2019
    count[mod] += 1
    tmp *= 10
    tmp %= 2019
count[0] += 1
print(sum((item*(item-1)//2 for item in count.values())))
### BUGGY CODE ###

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)

    # divisors.sort()
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  for j in range(i, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

### FIXED CODE ###

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
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  b = n // d[i]
  if b == d[i]:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if b == d[j]:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)
### BUGGY CODE ###

n = input()
a = list(map(int, input().split()))
cut=0
 
while all(i%2==0 for i in a):
  list=[i/2 for i in a]
  cut+=1
print(cut)

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
cnt = 0
while all(i%2==0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
### BUGGY CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[100000001 for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
q = int(input())

flag = True
ans = s
for i in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    flag = not flag
  else:
    if int(query[1]) == 1:
      if flag:
        ans = query[2] + ans
      else:
        ans+=query[2]
    else:
      if flag:
        ans+=query[2]
      else:
        ans = query[2] + ans

if flag:
  for i in ans:
    print(i, end="")
else:
  t = ans[::-1]
  for i in t:
    print(i, end="")



### FIXED CODE ###

s = input()
q = int(input())
revFlag = False
head, tail = [], []

for i in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    revFlag = not revFlag
  else:
    if int(query[1]) == 1:
      if not revFlag:
        head.append(query[2])
      else:
        tail.append(query[2])
    else:
      if not revFlag:
        tail.append(query[2])
      else:
        head.append(query[2])

if not revFlag:
  h = "".join(reversed(head))
  t = "".join(tail)
  print("".join([h, s, t]))
else:
  h = "".join(head)
  t = "".join(reversed(tail))
  print("".join([t, s[::-1], h]))
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result % (10 ** 9 + 7)

n, k = map(int, input().split())
sortedList = sorted(list(map(int, input().split())))

result = 0
for i in range(1, n - k + 2):
  result = (result + cmb(n - i, k - 1) * (sortedList[n - i] - sortedList[i - 1])) % (10 ** 9 + 7)
print(result)


### FIXED CODE ###

n, k = map(int, input().split())
sortedList = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7

factorial = [1]
for i in range(1, n + 1):
  factorial.append((factorial[i - 1] * i) % mod)

def cmb(n, k):
  return factorial[n] * pow(factorial[n - k], mod - 2, mod) * pow(factorial[k], mod - 2, mod)

result = 0
for i in range(1, n - k + 2):
  val = cmb(n - i, k - 1) * (sortedList[n - i] - sortedList[i - 1])
  result += val
print(result % mod)