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

import sys


n = int(input())

primary = [0] * 1000
secondary = [0] * 1000


for i in range(n):
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()

    len1 = len(s1)
    len2 = len(s2)

    for i in range(len1):
        primary[i] = 0
        secondary[i] = 0

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matched = 1
            else:
                matched = 0

            if j == 0:
                secondary[j] = matched
            else:
                sc0 = secondary[j-1]
                pr0 = primary[j-1] + matched
                pr1 = primary[j]
                if sc0 > pr0:
                    if pr0 > pr1:
                        secondary[j] = sc0
                    elif sc0 > pr1:
                        secondary[j] = sc0
                    else:
                        secondary[j] = pr1
                else:
                    if sc0 > pr1:
                        secondary[j] = pr0
                    elif pr0 > pr1:
                        secondary[j] = pr0
                    else:
                        secondary[j] = pr1

        primary, secondary = secondary, primary

    print(primary[len1-1])



### FIXED CODE ###

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()
### BUGGY CODE ###

S = input()
N = len(S)
S = int(S, 2)

a = 0
two = 2
b = 2**N -1
for n in range(N//2):
	a += two
	two *= 4
b = b^a
a = a ^ S
b = b ^ S
at = 0
bt = 0
for n in range(N):
	at += a%2
	bt += b%2
	a //= 2
	b //= 2
print(min(at, bt))

### FIXED CODE ###

S = input()
N = len(S)
t0, t1 = 0, 1
a = 0
b = 0
for s in S:
	if s == "1":
		a += t0
	else:
		a += t1
	t0, t1 = t1, t0
print(min(a,N-a))
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 1 
for i in a:
    ans *= i
    if ans > 10**18:
        ans = -1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 1 
if 0 in a:
    print(0)
    sys.exit(0)
for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit(0)
print(ans)
### BUGGY CODE ###

N = int(input())
n = N
L = []

print(str(N) + ': ', end = '')

for i in range(2, n+1):
    while n%i == 0:
        n = n/i
        L.append(i)
        #print(' ' + str(i), end = '')

print(' '.join(map(str, L)))



### FIXED CODE ###

N = int(input())
n = N
m = N ** 0.5
L = []
i = 3

print(str(N) + ': ', end = '')

while n%2 == 0:
    n = n/2
    L.append(2)

while i <= m:
    while n%i == 0:
        n = n/i
        L.append(i)
    i += 2

if n not in L:
    L.append(int(n))  

if 1 in L:
    L.remove(1)

if len(L) == 0:
    L.append(N)

print(' '.join(map(str, L)))
### BUGGY CODE ###

input = raw_input
n, k = map(int, input().split(" "))
ps = map(int, input().split(" "))

means = [(1+p)/2. for p in ps]

for i in range(n-k+1):
    cur = sum(means[i:i+k])
    if i == 0:
        out = cur
    else:
        out = max(cur, out)

print(out)

### FIXED CODE ###

input = raw_input
n, k = map(int, input().split(" "))
ps = map(int, input().split(" "))

means = [(1+p)/2. for p in ps]

for i in range(n-k+1):
    if i == 0:
        cur = sum(means[i:i+k])
        out = cur
    else:
        cur = cur - means[i-1] + means[i+k-1]
        out = max(cur, out)

print(out)
### BUGGY CODE ###

a, b, k = map(lambda x: int(x), input().split())

for i in range(k):
  if a > 0:
    a = a - 1
  elif b > 0:
    b = b - 1

print('{} {}'.format(a, b))
    

### FIXED CODE ###

a, b, k = map(lambda x: int(x), input().split())

if a >= k:
  print('{} {}'.format(a-k, b))
elif b >= (k-a):
  print('{} {}'.format(0, b-(k-a)))
else:
  print('{} {}'.format(0, 0))
### BUGGY CODE ###

import bisect
n = int(input())
s = input()
R = []
G = []
B = []
for i in range(n):
  if s[i] == 'R':
    R.append(i)
  elif s[i] == 'G':
    G.append(i)
  else:
    B.append(i)
res = 0
for i in range(n):
  if s[i] == 'R':
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(B, G[j])
      res += len(B) - y
      sss.add(2*G[j]-i)
    res -= len(sss & set(B))
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(G, B[j])
      res += len(G) - y
      sss.add(2*B[j]-i)
    res -= len(sss & set(G))
  elif s[i] == 'G':
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(R, B[j])
      res += len(R) - y
      sss.add(2*B[j]-i)
    res -= len(sss & set(R))
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(B, R[j])
      res += len(B) - y
      sss.add(2*R[j]-i)
    res -= len(sss & set(B))
  else:
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(R, G[j])
      res += len(R) - y
      sss.add(2*G[j]-i)
    res -= len(sss & set(R))
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(G, R[j])
      res += len(G) - y
      sss.add(2*R[j] - i)
    res -= len(sss & set(G))
print(res)

### FIXED CODE ###

import bisect
n = int(input())
s = input()
R = []
G = []
B = []
for i in range(n):
  if s[i] == 'R':
    R.append(i)
  elif s[i] == 'G':
    G.append(i)
  else:
    B.append(i)
Rs = set(R)
Bs = set(B)
Gs = set(G)
res = 0
for i in range(n):
  if s[i] == 'R':
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(B, G[j])
      res += len(B) - y
      sss.add(2*G[j]-i)
    res -= len(sss & Bs)
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(G, B[j])
      res += len(G) - y
      sss.add(2*B[j]-i)
    res -= len(sss & Gs)
  elif s[i] == 'G':
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(R, B[j])
      res += len(R) - y
      sss.add(2*B[j]-i)
    res -= len(sss & Rs)
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(B, R[j])
      res += len(B) - y
      sss.add(2*R[j]-i)
    res -= len(sss & Bs)
  else:
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(R, G[j])
      res += len(R) - y
      sss.add(2*G[j]-i)
    res -= len(sss & Rs)
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(G, R[j])
      res += len(G) - y
      sss.add(2*R[j] - i)
    res -= len(sss & Gs)
print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
A_list = list(map(int,input().split()))
A_index = set(A_list)
A_count = [ A_list.count(A) for A in A_index]
A_count.sort()
A_len = len(A_count)
print(sum([A_count[i] for i in range(A_len - K)]))


### FIXED CODE ###

N, K = map(int, input().split())
A_list = list(map(int,input().split()))
A_dict = dict()
for elem in A_list:
    if not elem in A_dict:
        A_dict[elem] = 1
    else:
        A_dict[elem] += 1
total = 0
A_dict = sorted(A_dict.items(), key=lambda x: x[1])
for i in range(len(A_dict) - K):
    total += A_dict[i][1]
print(total)
### BUGGY CODE ###

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

set_a = set(li_a)

for i in range(1, n + 1):
    if i in set_a:
        print(li_a.count(i))
    else:
        print(0)


### FIXED CODE ###

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

dic = {}
for a in li_a:
    dic[a] = dic.get(a, 0) + 1

for i in range(1, n + 1):
    print(dic.get(i, 0))
### BUGGY CODE ###

import fractions
K = int(input())
A = [i for i in range(1, K+1)]
B = [i for i in range(1, K+1)]
C = [i for i in range(1, K+1)]
 
cnt = 0
for a in A:
  for b in B:
    for c in C:
      N = [a,b,c]
      ans = N[0]
      for i in range(1, 3):
        ans = fractions.gcd(ans, N[i])
      cnt += ans
print(cnt)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
K = int(input())
A = B = C = [i for i in range(1, K+1)]

L = [gcd(a,b) for a in A for b in B]

cnt = sum([gcd(l,c) for l in L for c in C])   
print(cnt)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
dp_prev = [float("inf") for i in range(2**n)]
dp_next = [float("inf") for i in range(2**n)]
dp_prev[0] = 0
s = {0}

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    s_next = set()

    for j in s:
        dp_next[j|c] = min(dp_prev[j|c], dp_prev[j] + a, dp_next[j|c])
        dp_next[j] = min(dp_prev[j], dp_next[j])
        s_next.add(j|c)

    dp_prev = dp_next[:]
    s |= s_next

print([dp_next[-1], -1][dp_next[-1] == float("inf")])


### FIXED CODE ###

n, m = [int(i) for i in input().split()]
dp = [[float("inf") for i in range(2**n)] for j in range(m+1)]
dp[0][0] = 0

for i in range(m):
    a, _ = [int(_) for _ in input().split()]
    c = sum([2**(int(_)-1) for _ in input().split()])

    for j in range(2**n):
        dp[i+1][j|c] = min(dp[i][j|c], dp[i][j] + a, dp[i+1][j|c])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

print([dp[-1][-1], -1][dp[-1][-1] == float("inf")])
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        if a_cnt[n] > 1:
            return True

        # divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i in a_set and i != n:
                    return True
                if i != n // i:
                    if n // i in a_set and n//i != n:
                        return True

        return False

    ans = 0
    for ai in a_set:
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)
    lista = list(seta)
    lista.sort()

    table = [True for _ in range(10 ** 6 + 1)]
    ans = 0

    for ai in lista:
        if table[ai]:
            if cnta[ai] == 1:
                ans += 1
            for i in range(ai, 10 ** 6 + 1, ai):
                table[i] = False

    print(ans)


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

K=int(input())
ANS=[]
for i in range(1,10**6*2):
  LEN=len(str(i))
  STR=str(i)
  if LEN==1:
    ANS+=[i]
  for k in range(LEN-1):
    if abs(int(STR[k])-int(STR[k+1]))>1:
      break
    if k==LEN-2:
      ANS+=[i]
ans=ANS[K-1] 
print(ans)

### FIXED CODE ###

K=int(input())
ANS=[i for i in range(1,10)]
i=0
while len(ANS)<=10**5:
  last=str(ANS[i])[-1]
  if last=="0":
    ANS+=[ANS[i]*10,ANS[i]*10+1]
  elif last=="9":
    ANS+=[ANS[i]*10+8,ANS[i]*10+9]
  else:
    ANS+=[ANS[i]*10+int(last)-1,ANS[i]*10+int(last),ANS[i]*10+int(last)+1]
  i+=1  
ans=ANS[K-1]
print(ans)
### BUGGY CODE ###

n = int(input())
upper = 1e18
res = 1
for x in map(int, input().split()):
   res *= x
print(-1 if res > upper else res)

### FIXED CODE ###

n = int(input())
upper = 1e18
res = 1
generator = map(int, input().split())
for x in generator:
   res *= x
   if res > upper:
      break

for x in generator:
   if x == 0:
      res = 0
   
print(-1 if res > upper else res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    ans=0
    que=deque()
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.popleft()
            for ddx in (-1,1,-N,N):
                nx=x+ddx
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)
### BUGGY CODE ###

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

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

print(c)

### FIXED CODE ###

k, s = map(int, input().split())
c = 0

for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if z >= 0 and z <= k:
            c += 1
print(c)
### BUGGY CODE ###

import numpy as np
import bisect
n,m,q = map(int,input().split())
lr = []
s = []
for i in range(m):
    l = list(map(int,input().split()))	
    lr.append(l)
    s.append(l[0])
lr.sort()
s.sort()

ass = np.zeros((n,n))
#print(ass)
#print(lr)

for i in range(n):
    k = bisect.bisect_left(s,i+1)
    
    for j in range(k,m):
        ass[i][lr[j][1]-1]+=1
        
#print(ass)

for i in range(q):
    p,qa = map(int,input().split())
    ans = sum(ass[p-1][:qa:])
    print(int(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1

for i in range(n):
    for j in range(1,n):
        res[i][j] += res[i][j-1]
for i in range(n):
    for j in range(1,n):
        res[j][i] += res[j-1][i]
for i in range(q):
    p,q = map(int,input().split())
    print(res[q-1][p-1])
### BUGGY CODE ###

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

for i in range(q):
    b,c = map(int,input().split())
    a = [c*(a[j]==b)+a[j]*(a[j]!=b) for j in range(n)]
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
a_dict = dict()
for i in a:
    if i in a_dict:
        a_dict[i] = a_dict[i] + 1
    else:
        a_dict[i] = 1
a_sum = sum(a)

for i in range(q):
    b,c = map(int,input().split())
    if not b in a_dict:
        print(a_sum)
        continue
    a_sum = a_sum - a_dict[b]*b + a_dict[b]*c
    if c in a_dict:
        a_dict[c] = a_dict[c] + a_dict[b]
    else:
        a_dict[c] = a_dict[b]
    a_dict[b] = 0
    print(a_sum)
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split(" "))

score_list = np.array([K] * N)

for q in range(Q):
    i = int(input())

    subtract = np.array([-1] * N)
    subtract[i - 1] += 1

    score_list = score_list + subtract

for cond in (score_list > 0):
    print("Yes" if cond else "No")

### FIXED CODE ###

N, K, Q = map(int, input().split(" "))

score_list = [K - Q] * N

for q in range(Q):
    i = int(input())
    score_list[i - 1] += 1

for s in score_list:
    if s > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

for i in range(1, N+1):
    tmp = 0
    for a in A:
        if a == i:
            tmp+=1
    print(tmp)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
score = [0 for _ in range(N)]

for a in A:
    score[a-1] += 1

for s in score:
    print(s)
### BUGGY CODE ###

n=int(input())
a=[[0 for i in range(2)] for j in range(n)]
for i in range(n):
    a[i][1],a[i][0]=map(int,input().split())
b=sorted(a)
c=[b[i][1] for i in range(n)]
ans="Yes"
for i in range(n):
    if b[i][0]<sum(c[:i+1]):
        ans="No"
print(ans)

### FIXED CODE ###

n=int(input())
# a=[[0]*2]*n
a=[[0 for i in range(2)] for j in range(n)]
for i in range(n):
    a[i][1],a[i][0]=map(int,input().split())
b=sorted(a)
c=[b[i][1] for i in range(n)]
ans="Yes"
d=0
for i in range(n):
    d+=c[i]
    if b[i][0]<d:
        ans="No"
        break
print(ans)
### BUGGY CODE ###

# coding: utf-8

if __name__ == '__main__':
    n = int(input())
    p = 1
    for i in range(n):  #range(10) は [0,1,2,3,4,5,6,7,8,9] を表す
        p = p * (i+1)
    print(p % int(1e9 + 7))


### FIXED CODE ###

# coding: utf-8

if __name__ == '__main__':
    n = int(input())
    p = 1
    for i in range(n):  #range(10) は [0,1,2,3,4,5,6,7,8,9] を表す
        p *= (i+1)
        p %= int(1e9 + 7)
    print(p)
### BUGGY CODE ###

from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    p = []
    for i in reversed(range(n)):
        if a[i]:
            p.append(i + 1)
            u = 1
            v = i + 1
            while u * u <= v:
                if v % u == 0:
                    a[u - 1] ^= 1
                    if u != v // u:
                        a[v // u - 1] ^= 1
                u += 1
    if len(p) > 0:
        print(len(p))
        print(*p)
    else:
        print(0)
main()

### FIXED CODE ###

from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    p = []
    for i in reversed(range(n)):
        if a[i]:
            p.append(i + 1)
            u = 1
            v = i + 1
            while u * u <= v:
                if v % u == 0:
                    a[u - 1] ^= 1
                    if u != v // u:
                        a[v // u - 1] ^= 1
                u += 1
    if len(p) > 0:
        print(len(p))
        print(*p)
    else:
        print(0)
main()
### BUGGY CODE ###

s = input()
k = int(input())
sub = []
for i in range(0,len(s)):
    j = 1
    while i+j<=len(s):
        if not s[i:i+j] in sub:
            sub.append(s[i:i+j])
        j = j + 1
sub.sort()
print(sub[k-1])

### FIXED CODE ###

s = input()
k = int(input())
sub = set()
for i in range(0,len(s)):
    j = 1
    while i+j<=len(s) and j<=5:
        sub.add(s[i:i+j])
        j = j + 1
ans = list(sub)
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append([int(x) for x in input().split()])

total = 0

for x in range(1, M + 1):
    max = 0
    max_index = -1
    for y, row in enumerate(A):
        if row[0] <= x and row[1] > max:
            max = row[1]
            max_index = y
    if max_index != -1:
        total += max
        A.pop(max_index)

print(total)





### FIXED CODE ###

from collections import defaultdict
import heapq

N, M = [int(x) for x in input().split()]

dict = defaultdict(list)
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    dict[A].append(B)

h = []
total = 0
for x in range(1, M + 1):
    for y in dict[x]:
        heapq.heappush(h, -y)
    if h:
        total += heapq.heappop(h)

print(-total)
### BUGGY CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   ans = max(max(z_algo(s[i:])[ceil(len(z_algo(s[i:])), 2):]), ans)

print(ans)

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   for idx, j in enumerate(z_algo(s[i:])):
      ans = max(min(idx, j), ans)

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

s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=[list(map(int,input().split())) for i in range(s[1])]
a=0
for i in range(s[1]):
  for j in range(u[i][0]):
    t.append(u[i][1])
t.sort()
for l in range(s[0]):
  a = a+t[len(t)-l-1]
print(a)


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[list(map(int,input().split())) for _ in range(M)]
B.sort(key=lambda x:-x[1])
i,j=0,0
while i<=N-1:
  for l in range(B[j][0]):
    if A[i]>=B[j][1]:
      print(sum(A))
      exit()
    A[i]=B[j][1]
    i+=1
    if i==N:
      print(sum(A))
      exit()
  j+=1
  if j==M:
    print(sum(A))
    exit()
print(sum(A))