Harryxun/stf_run huggingface dataset:
total = int(input())
text = input()

res = 0

for x in range(0, total - 1):
    if text[x] == "A":
        if x + 2 <= total:
            if text[x + 1] == "B" and text[x + 2] == "C":
                res += 1

print(res)

### FIXED CODE ###

total = int(input())
text = input()

res = 0

if total >= 3:
    for x in range(0, total - 1):
        if text[x] == "A":
            if x + 3 <= total:
                if text[x + 1] == "B" and text[x + 2] == "C":
                    res += 1

print(res)
n=int(input())
if n==1:print('Hello World')
else:
    a=int(input())
    b=int(inputt())
    print(a+b)

### FIXED CODE ###

n=int(input())
if n==1:print('Hello World')
else:
    a=int(input())
    b=int(input())
    print(a+b)
a,b,c=map(int,input().split())
n=int(input())
arr=[a,b,c]
arr=sort(arr)
print(arr[0]+arr[1]+arr[2]*(2**n))

### FIXED CODE ###

arr=list(map(int,input().split()))
n=int(input())
arr=sorted(arr)
print(arr[0]+arr[1]+arr[2]*(2**n))
import pandas as pd
n = int(input())
S = []
for _ in range(n):
    S.append(input()) 
df = pd.DataFrame(S)
print(len(pd.unique(df[0])))

### FIXED CODE ###

import collections
n = int(input())
S = []
for _ in range(n):
    S.append(input()) 
print(len(collections.Counter(S)))
def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for v,w in zip(values,weights):
        for c in range(w, capacity+1):
            work[c]=max(work[c],work[c-w]+v)
    return work[-1]
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))+[1]
    prices_b=list(map(int,inp().split()))+[1]
    
    valA,_=knapsack_123(values=prices_b,weights=prices_a,capacity=n)
    print(valA)
    valB,_=knapsack_123(values=prices_a,weights=prices_b,capacity=valA)
    return '{}'.format(valB)
print(sol())

### FIXED CODE ###

def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for v,w in zip(values,weights):
        for c in range(w, capacity+1):
            work[c]=max(work[c],work[c-w]+v)
    return work[-1]
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))+[1]
    prices_b=list(map(int,inp().split()))+[1]
    
    valA=knapsack_123(values=prices_b,weights=prices_a,capacity=n)
    valB=knapsack_123(values=prices_a,weights=prices_b,capacity=valA)
    return '{}'.format(valB)
print(sol())
k=input()
s=input()

if len(s)<=k:
    print(s)
else:
    print(s+"...")

### FIXED CODE ###


k=int(input())
s=input()

#if len(s)<=k:
    #  print(s)
    #else:
    #print(s+"...")





#########他人のコピー#########


if len(s)<=k:
      print(s)
else:
    print(s[:k] + '...')
    

#########他人のコピー#########
n, y = map(int, input().split())

#.
y = y // 1000

#.
for i in range(n+1):
    for j in range(n+1):
        #.
        money = y - i*10 - j*50

        #.
        if money == n - i - j:
            print("{} {} {}".format(i, j, money))
            return 0


### FIXED CODE ###

def solve(args):
    n, y = args

    #.
    for i in range(n+1):
        for j in range(0, n-i+1):
            #.
            k = n - i - j

            #.
            if i*10000 + j*5000 + k*1000 == y:
                return "{} {} {}".format(i, j, k)

    return "-1 -1 -1"

print(solve(map(int, input().split())))
import math

N,X = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
d = [abs(X-i) for i in x if abs(X-i)!=0]

gcd = d[0]
for i in range(len(d)-1):
    gcd = math.gcd(gcd,d[i+1])

print(gcd)

### FIXED CODE ###

import fractions

N,X = (int(i) for i in input().split())
x = [int(i) for i in input().split()]
#d = [abs(X-i) for i in x if abs(X-i)!=0]
d = [abs(X-i) for i in x]

gcd = d[0]
i=1
while True:
    if i>=N:
        break
    gcd = fractions.gcd(gcd,d[i])
    i=i+1 

print(gcd)
N = int(input())
K = int(input())

a = N // K
b = abs(N - (K*a))
c = abs(N - (K*(a+1)))
print(min(b, c))

### FIXED CODE ###

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

a = N // K
b = abs(N - (K*a))
c = abs(N - (K*(a+1)))
print(min(b, c))
N = int(input())
A = list(map(int, input().split()))

ct = collections.Counter(A)

ret = []
total = 0
for k,count in ct.items():
    if count > 1:
        total += count * (count-1) // 2

for i,v in enumerate(A):
    if ct[v] > 1:
        count = ct[v]
        adjust = (count-1) * (count-2) // 2 - (count-1) * count // 2
        val = str(total + adjust)
    else:
        val = '0'
    print(val)
    

### FIXED CODE ###


import collections

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

ct = collections.Counter(A)

ret = []
total = 0
for k,count in ct.items():
    if count > 1:
        total += count * (count-1) // 2

for i,v in enumerate(A):
    if ct[v] > 1:
        count = ct[v]
        adjust = (count-1) * (count-2) // 2 - (count-1) * count // 2
        val = total + adjust
    else:
        val = total
    print(val)
from math import gcd
def lcm(i,j):
  return i * j // gcd(i,j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p,q,r,b = lst[n]
      if weight[n] != -1:pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p,q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight(r) * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0,n):
      if weight[i + 1] == -1:
        setWeight(i+1)
    print(max(weight))
if __name__ == '__main__':
  main()



### FIXED CODE ###


from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight[r] * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()
import numpy as np
n,l=int(input()),list(map(float,input().split()))
dp=np.full([n+1,n+1],0.0)
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][((n+1)//2):]))


### FIXED CODE ###

n,l=int(input()),list(map(float,input().split()))
dp=[[0.0]*(n+1) for _ in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][((n+1)//2):]))
import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

a = sorted(li,key = lambda x:-x[1])


for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])

a = sorted(li,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")


### FIXED CODE ###

import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]
s=[]
a = sorted(a,key = lambda x:-x[1])

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])
c=set(c)
a = sorted(a,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    else:
        s.append(a[i][1])

    #if a[i][1] in c:
s=set(s)

for i in s:
    if i in c:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")
n=int(input())
l=list(map(int, input().split()))
m=pop(max(l))
print("Yes" if m < sum(l) else "No")

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
print("Yes" if max(L) < sum(L)-max(L) else "No")
n, m = map(int, input().split())
res = [0,10**5]
for i in ragne(m):
    l, r = map(int, input().split())
    res[0] = max(res[0], l)
    res[1] = min(res[1], r)

print(max(res[1]-res[0]+1),0)

### FIXED CODE ###

n, m = map(int, input().split())
res = [0,10**5]
for i in range(m):
    l, r = map(int, input().split())
    res[0] = max(res[0], l)
    res[1] = min(res[1], r)

print(max(res[1]-res[0]+1,0))
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    temp = A[now:now+C_B[j][1]]
    #print(temp)
    if C_B[j][0]>=temp[-1]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
    elif C_B[j][0]<=temp[0]: #置き換えない
        break
    else:
        sm = 0
        la = len(temp)-1
        md = C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            if temp[md]<p:
                sm=md
                md=(la-sm)//2
            elif temp[md]==p:
                la=md
            else:
                la=md
                md=(la-sm)//2
        sums += la*p
        now += la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

### FIXED CODE ###

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

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)
def run(n, x, xx):
    xx.append(x)
    xx = sorted(xx)
    d = [xx[i+1]-xx[i] for i in range(n)]
    d = sorted(d)
    min_d = d[0]
    if len(d) == 1:
        return min_d
    for i in range(1, len(d)):
        min_d = fractions.gcd(min_d, d[i])
    return min_d


def main():
    n, x = map(int, input().split())
    xx = list(map(int, input().split()))
    print(run(n, x, xx))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions


def run(n, x, xx):
    xx.append(x)
    xx = sorted(xx)
    d = [xx[i+1]-xx[i] for i in range(n)]
    d = sorted(d)
    min_d = d[0]
    if len(d) == 1:
        pass
    else:
        for i in range(1, len(d)):
            min_d = fractions.gcd(min_d, d[i])
    return min_d


def main():
    n, x = map(int, input().split())
    xx = list(map(int, input().split()))
    print(run(n, x, xx))


if __name__ == '__main__':
    main()
from bisect import bisect_right
from collections import deque

n,m = map(int,input().split())
aa = list(map(int,input().split()))
q = deque()
q.extend(sorted(aa))

for i in range(m):
  tmp = q.pop()//2  
  pos = bisect_right(q,tmp)
  q.insert(pos,tmp)
  
print(sum(q))  

### FIXED CODE ###

# dequeにinsert追加されたのは 3.5 から
from heapq import heappop,heappush,heapify
n,m = map(int,input().split())
aa = list(map(int,input().split()))
aa = list(map(lambda x:-x,aa))

heapify(aa)
for i in range(m):
  tmp = heappop(aa)  
  heappush(aa,-(-tmp//2))

print(-sum(aa))
from functools import lru_cache
 
@lru_cache(maxsize=1e6)
def n_th_prime(n):
    if n == 0:
        return 2
    while True:
        for i in range(n):
            if x % n_th_prime(i) == 0:
                break
        else: return(x)
        x += 1

x = int(input())

k=0
while True:
    a = n_th_prime(k)
    if x > a:
        k += 1
    else:
        print(a)

### FIXED CODE ###

from functools import lru_cache
 
@lru_cache(maxsize=100000)
def n_th_prime(n):
    if n == 0:
        return 2
    primes = [n_th_prime(k) for k in range(n)]
    k = 1
    x = primes[-1] + 1
    while True:
        for p in primes[:k]:
            if x % p == 0:
                x += 1
                break
        else:
            if x > p**2:
                k += 1
            else:
                return x

x = int(input())

k = 0
p = 2
while True:
    for i in range(k):
        p = n_th_prime(i)
        if x % p == 0:
            x += 1
            break
    else:
        if x > p**2:
            k += 1
        else:
            print(x)
            break
N,M =map(int,input().split())
if M>0:
    a = [0]*M
    for i in range(M):
        a[i] = int(input())

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0

SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(ans)

### FIXED CODE ###

def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()
from math import gcd

n = int(input())
a = list(map(int, input().split()))
fromLeft = [0] * n
fromLeft[0] = a[0]
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
fromRight = [0] * n
fromRight[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
    fromRight[i] = gcd(fromRight[i + 1], a[i])
ret = 0
for i in range(n):
    if i == 0:
        curGcd = fromRight[n - 2]
    elif i == n - 1:
        curGcd = fromLeft[n - 2]
    else:
        curGcd = gcd(fromLeft[i - 1], fromRight[n - i])
    ret = max(ret, curGcd)
print(ret)

### FIXED CODE ###

def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x

n = int(input())
a = list(map(int, input().split()))
fromLeft = [0] * n
fromLeft[0] = a[0]
fromRight = [0] * n
fromRight[0] = a[n - 1]
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
    fromRight[i] = gcd(fromRight[i - 1], a[n - i - 1])
ret = fromLeft[n - 1]
for i in range(n):
    if i == 0:
        curGcd = fromRight[n - 2]
    elif i == n - 1:
        curGcd = fromLeft[n - 2]
    else:
        curGcd = gcd(fromLeft[i - 1], fromRight[n - i - 2])
    ret = max(ret, curGcd)
print(ret)
from math import gcd 
n=int(input())
mod = 10**9+7
count = {}

for _ in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        continue
    if a*b != 0:
        g=gcd(a,b)*b//abs(b)
    elif a != 0:
        g=a
    else:
        g=b
        
    x=a//g,b//g
    count[x]=count.get(x,0)+1
        
mem=set()
ans=1
for (x,y),z in count.items():
    if (-1*x//abs(x)*y,abs(x)) in mem:
        continue
    mem.add((x,y))
    ans*=pow(2,z)+pow(2,count.get((-1*x//abs(x)*y,abs(x)),0))-1
    ans%=mod

print((ans-1)%mod)

### FIXED CODE ###

from math import gcd 
n=int(input())
mod = 10**9+7
count = {}

num=0
for _ in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        num+=1
        continue
    if a*b != 0:
        g=gcd(a,b)*(b//abs(b))
    elif a != 0:
        g=a
    else:
        g=b
        
    l=a//g,b//g
    count[l]=count.get(l,0)+1
        
mem=set()
ans=1
for (x,y),z in count.items():
    if x*y==0:
        k=(y,x)
    else:
        k=(-1*x//abs(x)*y,abs(x))
    if k in mem:
        continue
    mem.add((x,y))
    ans*=(pow(2,z)+pow(2,count.get(k,0))-1)
    ans%=mod

print((ans+num-1)%mod)
a,b,c,d=int(input().split())
a=int(a)
b=int(b)
c=int(c)
d=int(d)
list1=[]
list1.append(a*c)
list1.append(a*d)
list1.append(b*c)
list1.append(b*c)
list1.sort()
print(list1[3])

### FIXED CODE ###

a,b,c,d=input().split()
a=int(a)
b=int(b)
c=int(c)
d=int(d)
list1=[]
list1.append(a*c)
list1.append(a*d)
list1.append(b*c)
list1.append(b*d)
list1.sort()
print(list1[3])
s=[int(input()) for _ in range(5)]
k=[s[i]%10 for i in range(5)]
l=[]
for i in range(5):
    if k[i] !=0:
        l.append(10-k[i])
    else:
        l.append(0)
l=max(k)
m=sum(s)
n=sum(l)
print(int(m+n-l))

### FIXED CODE ###

s=[int(input()) for _ in range(5)]
k=[s[i]%10 for i in range(5)]
l=[]
for i in range(5):
    if k[i] !=0:
        l.append(10-k[i])
    else:
        l.append(0)
p=max(l)
m=sum(s)
n=sum(l)
print(int(m+n-p))
n = int(input())
l = list(map(int, input().split()))
u = list(set(l))
if len(u)==1 and u[0]==0:
  print("Yes")
elif n%3==0:
  if len(u)==2:
  	x = l.count(u[0])
  	y = l.count(u[1])
    if (x==2*n/3 and y==n/3) or (y==2*n/3 and x==n/3):
      print("Yes")
    else:
      print("No")
  elif len(u)==3:
    x = l.count(u[0])
  	y = l.count(u[1])
    z = l.count(u[2])
    if x==n/3 and y==n/3 and z==n/3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
u = list(set(l))
if len(u)==1 and u[0]==0:
  print("Yes")
elif n%3==0:
  if len(u)==2:
    x = l.count(u[0])
    y = l.count(u[1])
    if (x==2*n/3 and y==n/3 and u[1]==0) or (y==2*n/3 and x==n/3 and u[0]==0):
      print("Yes")
    else:
      print("No")
  elif len(u)==3:
    x = l.count(u[0])
    y = l.count(u[1])
    z = l.count(u[2])
    if x==n/3 and y==n/3 and z==n/3 and ((u[0]^u[1])^u[2])==0:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

i = 0
j = 0
c = []

if k < a[0] and k < b[0]:
    print(0)
    exit()

while True:
    if a[i] <= b[j]:
        c.append(a[i])
        i += 1
        if i == n -1:
            if j == m -1:
                break
            else:
                for l in range(j, m):
                    c.append(b[l])
                break
    else:
        c.append(b[j])
        j += 1
        if j == m -1:
            if i == n -1:
                break
            else:
                for l in range(i, m):
                    c.append(a[l])
                break

for i in range(len(c)):
    k -= c[i]
    if k < 0:
        print(i)
        exit()
    if i == len(c)-1:
        print(n+m)
        exit()

### FIXED CODE ###

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

best = 0

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])

ans , j = 0, M

for i in range(N +1):
    if a[i] > K:
        break
    while b[j] > K -a[i]:
        j -= 1
    ans = max(ans, i +j)
print(ans)
N = list(int(i) for i in input().split())

if abs(N[2]-N[0]) <= N[3]:
	print(“Yes”)
elif abs(N[1]-N[0])+abs(N[2]-N[1]) <= 2*N[3]:
	print(“Yes”)
else:
	print(“No”)

### FIXED CODE ###

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

if abs(c-a) <= d:
	print('Yes')
elif abs(b-a) <= d and abs(c-b) <= d:
	print('Yes')
else:
	print('No')
N,K=map(int, input().split())
A = list(map(int, input().split()))
B=0
for i in range(N-K+1):
    S = (sum(A[i:i+K])+K)/2
    if B<S:
        B=S
print(B)

### FIXED CODE ###

S,T=input().split()
A,B=map(int, input().split())
U=input()
if U==S:
    A -= 1
else:
    B -= 1
print(A,B)
ans = 0
for i in range(5):
	if int(input()) == 0:
		ans = i+1
print(ans)  


### FIXED CODE ###

a = list(map(int, input().split()))
for i in range(5):
  if a[i] == 0:
    print(i+1)
#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
dp = np.zeros((N+1, W+1), int)

for i in range(N):
    for j in range(W+1):
        if j-w[i] < 0:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = max(dp[i, j], dp[i, j-w[i]]+v[i])

print(dp[-1, -1])

### FIXED CODE ###

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
dp = np.zeros((N+1, W+1), int)

for i in range(N):
    dp[i+1, w[i]:] = np.maximum(dp[i, w[i]:], dp[i, :-w[i]] + v[i])
    dp[i+1, :w[i]] = dp[i, :w[i]]

print(dp[-1, -1])
L,R = map(int,input().split(' '))
if R - L >= 2019:
  print(0)
else:
  MIN = flaot('inf')
  for i in range(L,R):
    for j in range(i,R+1):
      MIN = min(MIN,(j-i) % 2019)
print(MIN)

### FIXED CODE ###

L,R = map(int,input().split(' '))
MIN = 2019
if R - L >= 2019:
  print(0)
else:
  for i in range(L,R):
    for j in range(i+1,R+1):
      A = i * j
      MIN = min(A%2019,MIN)
  print(MIN)
a, b, c = map(int, input().split())

if a+b+1 > c:
    count = b+c
else
    count = b+(a+b+1)

print(count)

### FIXED CODE ###


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

if a+b+1 > c:
    count = b+c
else:
    count = b+(a+b+1)

print(count)
N = int(input())
H = np.array(map(int, input().split()))
H = np.array([1,2,3,4,5])
tmp=[]
for i in range(len(H)-1):
    tmp.append(all([all(H[:i]<=[H[i]]), all([H[i]]<=H[i+1:])]))
print(sum(tmp))

### FIXED CODE ###

import numpy as np
N = int(input())
H = np.array(list(map(int, input().split())))
tmp = []
for i in range(1, len(H)):
    tmp.append(all(H[:i]<=H[i]))
print(sum(tmp)+1)
N, M = map(int, input().split())
A = list(map(int, input().split()))
ch = []
for _ in range(M):
    b, c = map(int, input().split())
    ch.append([c, b])

A.sort()
ch.sort(reverse = True)


n = -1
result = 0
fin = 0
for c, b in ch:
    if fin == 1:
        break

    n += b
    if n > N:
        for num in A[n-b+i+1:]:
            if c > num:
                result += c
            else:
                result += num

    if c < A[n]:
        for i, j in enumerate(A[n-b+1:]):
            if c < j:
                result += c*i + sum(A[n-b+i+1:])
                fin += 1
                break
    else:
        result += b * c


if not fin == 1:
    result += sum(A[n+1:])



print(result)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
ch = []
for _ in range(M):
    b, c = map(int, input().split())
    ch.append([c, b])

A.sort()
ch.sort(reverse = True)


n = -1
result = 0
fin = 0
for c, b in ch:
    if fin == 1:
        break

    n += b

    if n >= N:
        for num in A[n-b+1:]:
            if c > num:
                result += c
            else:
                result += num
            fin += 1
        break

    if c < A[n]:
        for i, j in enumerate(A[n-b+1:]):
            if c < j:
                result += c*i + sum(A[n-b+i+1:])
                fin += 1
                break
    else:
        result += b * c


if not fin == 1:
    result += sum(A[n+1:])



print(result)