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

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

for i in range(1, n):
    S[i] += S[i-1]

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    le -= 1
    u = q[1]
    du = q[0]
    V[u] = 1
    for i in range(len(M[u])):
        v = M[u][i][0]
        luv = M[u][i][1]
        if V[v] == 0:
            alt = du + luv
            if D[v] > alt:
                D[v] = alt
                P[v] = u
                heapq.heappush(Q, [alt, v])
                le += 1

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

for i in range(1, n):
    S[i] += S[i-1]

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, [alt, v])

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))

def sum(a, b):
    if b == 0:
        return a[b]
    else:
        return a[b] + sum(a, b-1)
sumA = []
for i in range(N):
    sumA.append(sum(A, i))

ans = 0

for i in range(N):
    if sumA[-1] // 2 > sumA[i]:
        continue
    else:
        if i == 0:
            ans = abs(sumA[i] * 2 - sumA[-1])
            break
        else:
            ans = min(abs(sumA[i] * 2 - sumA[-1]), abs(sumA[i-1] * 2 - sumA[-1]))
            break

print(ans)

### FIXED CODE ###

import sys
    
sys.setrecursionlimit(200000)
    
N = int(input())
A = list(map(int, input().split(' ')))
    

sumA = []
for i in range(N):
    if i == 0:
        sumA.append(A[i])
    else:
        sumA.append(sumA[-1] + A[i])
    
ans = 0
    
for i in range(N):
    if sumA[-1] // 2 > sumA[i]:
        continue
    else:
        if i == 0:
            ans = abs(sumA[i] * 2 - sumA[-1])
            break
        else:
            ans = min(abs(sumA[i] * 2 - sumA[-1]), abs(sumA[i-1] * 2 - sumA[-1]))
            break
    
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left

h,w=list(map(int,input().split()))
s=[]

lstw=[]
lsth=[]

for i in range(h):
    s.append([x for x in sys.stdin.readline().strip()])
    
    tw=[-1]
    for j in range(w):
        if s[i][j]=='#':
            tw.append(j)
    tw.append(w)

    lstw.append(tw)

for j in range(w):
    th=[-1]
    for i in range(h):
        if s[i][j]=='#':
            th.append(i)
    th.append(h)
    lsth.append(th)

ret=0

for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            continue

        posh=bisect_left(lsth[j],i)
        posw=bisect_left(lstw[i],j)

        cnth=lsth[j][posh]-lsth[j][posh-1]-1
        cntw=lstw[i][posw]-lstw[i][posw-1]-1

        ret=max(ret,cnth+cntw-1)

print(ret)

### FIXED CODE ###

import sys

h,w=list(map(int,input().split()))
s=[]

left=[[0]*w for _ in range(h)]
right=[[0]*w for _ in range(h)]
up=[[0]*w for _ in range(h)]
down=[[0]*w for _ in range(h)]

for i in range(h):
    s.append([x for x in sys.stdin.readline().strip()])

for i in range(h):
    cntl=0
    cntr=0
    for jl in range(w):
        jr=w-jl-1

        if s[i][jl]=='#':
            cntl=0
        else:
            cntl+=1
        
        if s[i][jr]=='#':
            cntr=0
        else:
            cntr+=1
        
        left[i][jl]=cntl
        right[i][jr]=cntr

for j in range(w):
    cntu=0
    cntd=0
    for iu in range(h):
        id=h-iu-1

        if s[iu][j]=='#':
            cntu=0
        else:
            cntu+=1
        
        if s[id][j]=='#':
            cntd=0
        else:
            cntd+=1
        
        up[iu][j]=cntu
        down[id][j]=cntd
ret=0

for i in range(h):
    for j in range(w):
        ret=max(ret,left[i][j]+right[i][j]+up[i][j]+down[i][j]-3)

print(ret)
### BUGGY CODE ###

import sys
N = int(input())
c = input()
ans = 0
exchange = 0
for i in range(N):
    if c[i] == "W":
        exchange = i
        break
else:
    print(0)
    sys.exit()

for i in range(N):
    # print(i+1,"回目")
    # print("exchange=",exchange)
    # print("c=",c)
    if N-1-i >exchange:
        if c[-(i+1)] =="R":
            c = list(c)
            c[exchange] = "R"
            c[-(i+1)] = "W"
            c = "".join(c)
            # c = c[:exchange]+"R"+c[exchange+1:]
            # print("newc=",c)
            # c = c[:-(i+1)]+"W"+c[-(i+1)+1:]
            # print("newc=",c)
            ans += 1
            for k in range(exchange+1,N):
                if c[k] == "W":
                    exchange = k
                    break
            else:
                break
    else:
        break
    
print(ans)

### FIXED CODE ###

import sys
N = int(input())
c = input()
ans = 0
exchange = 0
for i in range(N):
    if c[i] == "W":
        exchange = i
        break
else:
    print(0)
    sys.exit()

for i in range(N):
    if N-i > exchange:
        if c[-(i+1)] =="R":
            # c = list(c)
            # c[exchange] = "R"
            # c[-(i+1)] = "W"
            # c = "".join(c)
            # c = c[:exchange]+"R"+c[exchange+1:]
            # print("newc=",c)
            # c = c[:-(i+1)]+"W"+c[N-i:]
            # print("newc=",c)
            ans += 1
            for k in range(exchange+1,N-(i+1)):
                if c[k] == "W":
                    exchange = k
                    break
            else:
                break
    else:
        break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input().strip())
a_list = list(map(int, input().rstrip().split()))
#-----

a_list.sort(reverse=True)

Flag=True
cnt=0
while Flag:

    even_flag=False
    for i in range(len(a_list)):
    
        if a_list[i] % 2 == 1:
            #a_list[i] *= 3
            pass
        elif even_flag == False and a_list[i] != 0:
                a_list[i] /= 2
                even_flag = True
        
    if even_flag == True:
        cnt += 1
    else:
        Flag=False
        break

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input().strip())
a_list = list(map(int, input().rstrip().split()))
#-----

a_even_list=[]
for v in a_list:
    if v%2 == 0 and v != 0:
        a_even_list.append(v)

cnt=0
for v in a_list:
    while v%2 == 0 and v != 0:
        v /= 2
        cnt += 1

print(cnt)
### BUGGY CODE ###

n=int(input())
x,y,h=[0]*n,[0]*n,[0]*n
for i in range(n):
  x[i],y[i],h[i]=map(int,input().split())

for cx in range(101):
  for cy in range(101):
    for i in range(n):
      b=h[i]+abs(x[i]-cx)+abs(y[i]-cy)
      if i==0:
        if h[i]:
          s=set()
          s.add(b)
        else:
          s={i for i in range(b+1)}
      else:
        if h[i]:
          s&=set([b])
        else:
          s&={i for i in range(b+1)}
    if s:print(cx,cy,s.pop())

### FIXED CODE ###

import sys
n=int(input())

l=[list(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:-x[2])

for cx in range(101):
  for cy in range(101):
    for i in range(n):
      x,y,h=l[i]
      b=h+abs(x-cx)+abs(y-cy)
      if i==0:
        if h:
          s=set()
          s.add(b)
        else:
          s={i for i in range(b+1)}
      else:
        if not s:break
        if h:
          s&=set([b])
        else:
          s&=set(range(b+1))
    if s:
      print(cx,cy,s.pop())
      sys.exit()
### BUGGY CODE ###

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

count = [0] * n
for i in a:
    count[i-1] += 1

for i in range(n):
    ret = sum(count) - count[i]
    if ret >= k:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

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

count = [k - q] * n
for i in a:
    count[i-1] += 1

for i in range(n):
    if count[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N=int(input())
#m1,d1=map(int,input().split())
#hl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
S=list(input())
d=list('0123456789')
ans=0
for d1 in d:
    for d2 in d:
        for d3 in d:
            v=d1+d2+d3
            i=0
            p=0
            while i < N :
                if v[p]==S[i]:
                    p+=1
                    if p == 3:
                        break
                i+=1
            if p==3 :
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000,2000):
    templ=list(str(i))
    t=templ[1:]
    #print(t)
    p=0
    for q in range(n):
        if s[q]==t[p]:
            p+=1
        if p>2:
            ans+=1
            break         

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

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cl=[0 for i in range(n+1)]
for i in a:
    cl[i]+=1
for i in cl[1:]:
    print(i)
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


N = int(input())

ans = 1

if(N == 1):
    print(ans)
    exit()

for i in range(2, N+1):
    tmp = factorization(i)

#    print(tmp)
    sumnum = 1
    for j in tmp:
        sumnum *= (j[1]+1)

    ans += i * sumnum
#    print(ans)

print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())

Xarray = np.arange(1, N+1)
Xans = ((N // Xarray) * (2 * Xarray + ((N // Xarray) - 1) * Xarray)) // 2

print(sum(Xans))
### BUGGY CODE ###

a,b = map(int,input().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
max_gcd = gcd(a,b)

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table
    
table = sieve(max_gcd)

def cf(x,y):
    number = [1]
    for i in table:
        if x%i == 0 and y%i == 0:
            number.append(i)
        if i > max_gcd:
            break
    return number

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

s = cf(a,b)
cnt = 1
for i in s:
    t = is_prime(i)
    if t == True:
        cnt += 1

print(cnt)

### FIXED CODE ###

a,b = map(int,input().split())

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
  
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))

print(len(s&t) + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
n_list = list(map(int, input().split()))

#n = int(input())
#n_list = list(map(int, input().split()))

multi = 1

for i in range(n):
    multi *= n_list[i]

if multi<=1e18:
    print(multi)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
n_list = list(map(int, input().split()))

multi = 1
a = 1

for i in range(n):
    if n_list[i]==0:
        a = 0
        break

for i in range(n):
    if a == 0:
        multi = 0
        break

    multi *= n_list[i]

    if multi>1e18:
        break

if multi<=1e18:
    print(multi)
else:
    print(-1)
### BUGGY CODE ###

import math
n,m,k = map(int,input().split())
mod = 10**9+7
memo = {}
def factorial(num):
    if num == 0:
        return 1
    if not num in memo:
        memo[num] = num*factorial(num-1)
    return memo[num]

temp = math.factorial(n*m-2)//(math.factorial(k-2)*math.factorial(n*m-k))
ans = 0
for d in range(1,n):
    ans += d*((n-d)*(m**2))*temp
for d in range(1,m):
    ans += d*((m-d)*(n**2))*temp
print(ans%mod)

### FIXED CODE ###

n,m,k = map(int,input().split())
mod = 10**9+7
def combination(n,r,p):
    if n < r or r < 0:
        return 0
    r = min(n-r,r)
    
    fact = [1,1]
    factinv = [1,1]
    inv = [0,1]
    for i in range(2,n+1):
        fact.append((fact[-1]*i)%p)
        inv.append((-inv[p%i]*(p//i))%p)
        factinv.append((factinv[-1]*inv[-1])%p)
    return fact[n]*factinv[r]*factinv[n-r]%p
temp = combination(n*m-2,k-2,mod)
ans = 0
for d in range(1,n):
    ans += d*((n-d)*(m**2))*temp
for d in range(1,m):
    ans += d*((m-d)*(n**2))*temp
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    a = input()
    if not(a in s):
        s.append(a)
print(len(s))




### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    s = input()
    if not(s in d): d[s] = 1

print(len(d))
### BUGGY CODE ###

from collections import defaultdict
n,q=map(int,input().split())
s=input()
m=defaultdict(list)
for i in range(n):m[s[i]]+=[i]
g=[1]*n
for i in range(q):
	t,d=input().split()
	if d=="L":
		for i in m[t]:
			if i>0:g[i-1]+=g[i]
			g[i]=0
	else:
		for i in m[t]:
			if i<n-1:g[i+1]+=g[i]
			g[i]=0
print(sum(g))

### FIXED CODE ###

n,q=map(int,input().split())
s=" "+input()+" "
td=[input().split()for _ in[0]*q]
def test(x):
	for t,d in td:
		if s[x]==t:x+=1 if d=="R"else -1
	return x
def bs(b,g,t):
	while abs(b-g)>1:
		k=(b+g)//2
		if test(k)==t:g=k
		else:b=k
	return g
l=bs(n+1,0,0)
r=bs(0,n+1,n+1)
print(r-l-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
l = [0]*(10**6+1)

for i in a:
  if l[i] == 0:
    l[i] = 1
    for j in range(i*2,max(a)+1,i):
      l[j] = -1
  else:
    l[i] = -1
print(l.count(1))

### FIXED CODE ###

n = int(input())
a = sorted(map(int, input().split()))
l = [0]*(10**6+1)
M = max(a)

for i in a:
  if l[i] == 0:
    l[i] = 1
    for j in range(i*2, M+1, i):
      l[j] = -1
  else:
    l[i] = -1
print(l.count(1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000000)
input=sys.stdin.readline
N=int(input())

G = [[-1 for i in range(N)] for j in range(N)]
color = [0]*N

for i in range(N-1):
    e,f,g = list(map(int, input().split()))
    G[e-1][f-1]=g%2
    G[f-1][e-1]=g%2

def dfs(v,p,c):
    color[v]=c
    for i in range(N):
        if i==p:
            continue
        elif G[v][i] ==0 :
            dfs(i,v,c)
        elif G[v][i] ==1 :
            dfs(i,v,1-c)
        
dfs(0,-1,0)

for k in color:
    print(k)


### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
input=sys.stdin.readline
import heapq

N=int(input())

G = [[] for j in range(N)]

color = [0]*N

for _ in range(N-1):
    e,f,g = list(map(int, input().split()))
    heapq.heappush(G[e-1], [f-1,g%2])
    heapq.heappush(G[f-1], [e-1,g%2])

def dfs(v,p,c):
    color[v]=c
    for k in range(len(G[v])):
        i,j = heapq.heappop(G[v])
        if i==p:
            continue
        elif j ==0 :
            dfs(i,v,c)
        elif j ==1 :
            dfs(i,v,1-c)
        
dfs(0,-1,0)

for k in color:
    print(k)
### BUGGY CODE ###

K = int(input())
S = input()
L = len(S)
MOD = 10**9+7

MAXN = L+K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for i in range(K+1):
    ans += comb(L-1+K-i, L-1) * pow(25,K-i,MOD) * pow(26,i,MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
L = len(S)
MOD = 10**9+7

MAXN = L+K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for i in range(K+1):
    ans += comb(L-1+K-i, L-1) * pow(25,K-i,MOD) * pow(26,i,MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
M = list(map(int, input().split()))
M = sorted(M)
count = 0
for i in range(N):
  a = M[i]
  for j in range(i+1, N):
    b = M[j]
    upper = a+b
    #はー，二分探索掛けないんごー
    l, r = j, N
    while (r - l) > 1:
      c = (l + r + 1) // 2
      if M[c] < upper:
        l = c
      else:
        r = c  
    #print(count, j, l, r)
    count += l - j
      
print(count)

### FIXED CODE ###

N = int(input())
M = list(map(int, input().split()))
M = sorted(M)
count = 0
for i in range(N):
  a = M[i]
  for j in range(i+1, N):
    b = M[j]
    upper = a+b
    l, r = j, N
    while (r - l) > 1:
      c = (l + r) // 2
      if M[c] < upper:
        l = c
      else:
        r = c  
    #print(count, j, l, r)
    count += l - j
      
print(count)
### BUGGY CODE ###

# AtCoder Beginner Contest 131
# C - Anti-Division

A,B,C,D=map(int,input().split())
if C==1 or D==1:
    print(0)
    exit()

S=set()
sC=A//C -1
eC=B//C +1

sD=A//D -1
eD=B//D +1

for i in range (sC,eC):
    tC=C*i
    if A<=tC and tC<=B:
        S.add(tC)
    if tC>B:
        break


for i in range (sD,eD):
    tD=D*i
    if A<=tD and tD<=B:
        S.add(tD)
    if tD>B:
        break

print(B-A-len(S)+1)


### FIXED CODE ###

# AtCoder Beginner Contest 131
# C - Anti-Division
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A,B,C,D=map(int,input().split())
bc=B//C
ac=(A-1)//C
cnum=bc-ac

bd=B//D
ad=(A-1)//D
dnum=bd-ad


lcmcd=lcm(C,D)
blcmcd=B//lcmcd
alcmcd=(A-1)//lcmcd
lcmcdnum=blcmcd-alcmcd


print(B-A-cnum-dnum+lcmcdnum+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,X):
    if len(X) == 0:
        return N
    if len(X) == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if len(X) == 2:
        return max(X[0][1]*i + X[1][1]*((N-i*X[0][0])//X[1][0]) + (N-i*X[0][0])%X[1][0] for i in range(N//X[0][0]+1))
    if len(X) == 3:
        return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = sorted(filter(lambda c: int.__sub__(*c)<0, zip(*C)), reverse=True)
        N = small_dp(N, X)
    res = N

    return str(res)

if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

import collections
import fractions
N = int(input())
A = [int(i) for i in input().split()]


C = collections.Counter(A)

mod = 10**9 + 7

lcm = 1
for a in C.keys():
    lcm = lcm*a//fractions.gcd(lcm, a)
# print(lcm)

ans = 0
for k, v in C.items():
    ans += lcm//k*v
    ans %= mod
print(ans)


### FIXED CODE ###

import functools
import fractions
N = int(input())
A = [int(i) for i in input().split()]
S = set(A)


mod = 10**9 + 7


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(S)

ans = 0
for a in A:
    ans += lcm//a
    # ans %= mod
print(ans % mod)
### BUGGY CODE ###

H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if maze[y + dy][x + dx] == '.':
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)

### FIXED CODE ###

H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)
### BUGGY CODE ###

from heapq import heappop, heappush

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(int(x) for x in input().split()) for _ in range(m)]

h = []

for x in a:
    heappush(h, x)

for b, c in bc:
    for _ in range(b):
        temp = heappop(h)
        if temp >= c:
            heappush(h, temp)
            break
        else:
            heappush(h, c)

print(sum(h))



### FIXED CODE ###

from heapq import heappop, heappush

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(int(x) for x in input().split()) for _ in range(m)]

bc.sort(reverse=True)

h = []

for x in a:
    heappush(h, x)

for b, c in bc:
    for _ in range(b):
        temp = heappop(h)
        if temp >= c:
            heappush(h, temp)
            break
        else:
            heappush(h, c)

print(sum(h))