Harryxun/stf_run huggingface dataset:
w = raw_input().lower()
sum = 0
while True:
    t = raw_input().lower()
    if t == "END_OF_TEXT":
        break
    else:
        sum += t.count(w)
print sum

### FIXED CODE ###

w = raw_input().lower()
sum = 0
while True:
    t = raw_input().split()
    if t[0] == "END_OF_TEXT":
        break
    else:
        for ti in t:
            if ti.lower() == w:
                sum += 1
print sum
import bisect
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(index):
  if index == N:
    ans.append(-1)
    return
  num = a[index]
  if len(data[num]) == 1:
    ans.append(index)
    tami(index+1)
  elif index == data[num][-1]:
    ans.append(index)
    tami(data[num][0] +1)
  else:
    tmp = bisect.bisect_right(data[num],index)
    #print(num,data[num],tmp)
    tami(data[num][tmp]+1)

def judge(x):
  d = []
  d.append(a[x])
  while True:
    x += 1
    if x == N:
      break
    if len(data[a[x]]) == 1:
      d.append(a[x])
    elif x == data[a[x]][-1]:
      d.append(a[x])
    else:
      tmp = bisect.bisect_right(data[a[x]],x)
      x = data[a[x]][tmp]
  return d

N,K = IL()
a = IL()

data = [[] for i in range(N+1)]
ans = []

for i in range(N):
  data[a[i]].append(i)

#print(data)

tami(0)
#print(ans)
#print(len(ans),K)
#print(K%len(ans))

if ans == [-1] or K%len(ans) == 0:
  print()
else:
  print(" ".join(map(str,(judge(ans[K%len(ans)-1])))))
"""
for i in range(K):
  for j in range(N):
    if a[j] in data:
      num = data.index(a[j])
      data = data[:num]
    else:
      data.append(a[j])
  print(data)

11 10
1 2 3 0 4 5 6 0 4 5 6

11 10
3 1 4 1 5 9 2 6 5 3 5

10 10
1 4 8 3 5 4 2 3 4 6
"""

### FIXED CODE ###

import bisect
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(index):
  if index == N:
    ans.append(-1)
    return
  num = a[index]
  if len(data[num]) == 1:
    ans.append(index)
    tami(index+1)
  elif index == data[num][-1]:
    ans.append(index)
    tami(data[num][0]+1)
  else:
    tmp = bisect.bisect_left(data[num],index)
    #print(num,data[num],tmp)
    tami(data[num][tmp+1]+1)

N,K = IL()
a = IL()

data = [[] for i in range(200010)]
ans = []

for i in range(N):
  data[a[i]].append(i)

#print(data)

tami(0)

#print(ans)
#print(len(ans),K)
#print(K%len(ans))

if K%len(ans) == 0:
  print()
else:
  x = ans[K%len(ans)-1]
  d = []
  d.append(a[x])
  while x != N-1:
    x += 1
    if len(data[a[x]]) == 1:
      d.append(a[x])
    elif x == data[a[x]][-1]:
      d.append(a[x])
    else:
      tmp = bisect.bisect_left(data[a[x]],x)
      x = data[a[x]][tmp+1]

  print(" ".join(map(str,d)))

"""
for i in range(K):
  for j in range(N):
    if a[j] in data:
      num = data.index(a[j])
      data = data[:num]
    else:
      data.append(a[j])
  print(data)

11 10
1 2 3 0 4 5 6 0 4 5 6

11 10
3 1 4 1 5 9 2 6 5 3 5

10 10
1 4 8 3 5 4 2 3 4 6
"""
from math import gcd

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

A = (a-1) // c + (a-1) // d - (a-1) // ((c * d) // gcd(c, d))
B = b // c + b // d - b // ((c * d ) // gcd(c, d))

print (b - B - (a - 1 - A))

### FIXED CODE ###

from fractions import gcd

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

A = (a-1) // c + (a-1) // d - (a-1) // ((c * d) // gcd(c, d))
B = b // c + b // d - b // ((c * d ) // gcd(c, d))

print (b - B - (a - 1 - A))
b = input()
X = ['A', 'T']
Y = ['G', 'C']
print(str(X - b) if b in X else str(Y - b))

### FIXED CODE ###

b = input()
X = {'A', 'T'}
Y = {'G', 'C'}
print(''.join(X - {b}) if b in X else ''.join(Y - {b}))
N, K = map(int, input().split())

h = list(map(int(input().split())))

ans = 0
for i in h:
    if i>=K:
        ans+=1

print(ans)


### FIXED CODE ###

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

h = list(map(int,(input().split())))

ans = 0
for i in h:
    if i>=K:
        ans+=1


print(ans)
,N = map(int,input().split())
Ai = map(int, input().split())
 
if sum(A) >= H:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

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

sum=0
for Ai in A:
  sum += Ai

if sum >= H:
  print('Yes')
else:
  print('No')
import math

def fatora(n):
	ans = []
	for i in range(1, n+1):
		if i*i > n:
			break
		else:
			if n % i == 0:
				ans.append(i)
				ans.append(n//i)
	return set(ans)

def eh_primo(n):
	if n == 0:
		return False
	elif n == 1:
		return True
	elif n == 2:
		return True
	else:
		for i in range(2, n+10):
			if i*i > n:
				break
			else:
				if n % i == 0:
					return False
		return True



a, b = map(int, input().split())
new_gcd = math.gcd(a,b)

primos_qtd = 0

for num in fatora(new_gcd):
	if eh_primo(num):
		primos_qtd += 1
print(primos_qtd)

### FIXED CODE ###

def fatora(n):
	ans = []
	for i in range(1, n+1):
		if i*i > n:
			break
		else:
			if n % i == 0:
				ans.append(i)
				ans.append(n//i)
	return set(ans)

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a%b)


def eh_primo(n):
	if n == 0:
		return False
	elif n == 1:
		return True
	elif n == 2:
		return True
	else:
		for i in range(2, n+10):
			if i*i > n:
				break
			else:
				if n % i == 0:
					return False
		return True



a, b = map(int, input().split())
print(len(list(filter(eh_primo, fatora(gcd(a, b))))))
n=int(input())
a=sorted(list(map(int,input().split())))

l=[0]*100005
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(100005//a[i]):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)
            
        

### FIXED CODE ###

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

l=[0]*(1000005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(1000000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)
V=list(map(int,input().split()))
V0=Counter(V[::2]).most_common()
V1=Counter(V[1::2]).most_common()
ans=0
if V0[0][0]==V1[0][0]:
  if len(V0)==1 and len(V1)==1:
    print(N//2)
    exit()
  elif len(V0)!=1 and len(V1)!=1:
    if V0[1][0]>=V1[1][0]:
      V0[0],V0[1]=V0[1],V0[0]
    else:
      V1[0],V1[1]=V1[1],V1[0]
  elif len(V0)>len(V1):
     V0[0],V0[1]=V0[1],V0[0]
  else:
    V1[0],V1[1]=V1[1],V1[0]
for i in range(1,len(V0)):
  ans+=V0[i][1]
for i in range(1,len(V1)):
  ans+=V1[i][1]
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
v=list(map(int,input().split()))
a=Counter(v[0::2]).most_common()
b=Counter(v[1::2]).most_common()
a.append([0,0])
b.append([0,0])
if a[0][0]!=b[0][0]:
    print(n-(a[0][1]+b[0][1]))
else:
    print(min(n-(a[1][1]+b[0][1]),n-(a[0][1]+b[1][1])))
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 100#10**5+1
sch = [[0]*Mx for _ in range(C)]
scht = [0]*Mx
plist = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int,input().split())
    plist[c-1].append((s,t))
for c, p in enumerate(plist):
    p.sort()
    prevt = 0
    for s, t in p:
        if prevt == s:
            sch[c][prevt] = 0
        else:
            sch[c][s] = 1
        sch[c][t] = -1
        prevt = t
    for i in range(1, Mx):
        if sch[c][i]==1:
            scht[i-1]+=1
        if sch[c][i]==-1:
            scht[i]-=1

for i in range(1, Mx):
    scht[i] += scht[i-1]

print(max(scht))


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [[0]*Mx for _ in range(C)]
scht = [0]*Mx
plist = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int,input().split())
    plist[c-1].append((s,t))
for c, p in enumerate(plist):
    p.sort()
    prevt = 0
    for s, t in p:
        if prevt == s:
            sch[c][prevt] = 0
        else:
            sch[c][s] = 1
        sch[c][t] = -1
        prevt = t
    for i in range(1, Mx):
        if sch[c][i]==1:
            scht[i-1]+=1
        if sch[c][i]==-1:
            scht[i]-=1

for i in range(1, Mx):
    scht[i] += scht[i-1]

print(max(scht))
N, M = map(int, input().split())
a_k = [list(map(int, input().split())) for i in range(N)]
a_k.sort()

for i in range(1, len(a_k)):
    a_non = []
    if len(a_k[0]) <= 1:
        break

    for j in range(1, len(a_k[0])):
        if a_k[0][j] not in a_k[i][1:]:
            a_non.append(j)

    for j in range(len(a_non)):
        a_k[0].pop(a_non[j])


print(len(a_k[0]) - 1)


### FIXED CODE ###

N, M = map(int, input().split())
k = [i[1:] for i in [list(map(int, input().split())) for i in range(N)]]
k_1 = [flatten for inner in k for flatten in inner]
count_k = 0
for i in range(1, M + 1):
    if k_1.count(i) == N:
        count_k += 1

print(count_k)
N,A,B = map(int, input().split())
  
N -= 1
A -= 1
B -= 1

ans = 0
distAB = B - A

if distAB % 2 == 0:
    ans = distAB / 0

print(int(ans))


### FIXED CODE ###

from decimal import *
N,A,B = map(int, input().split())

N -= 1
A -= 1
B -= 1

ans = 0
distAB = B - A

if distAB % 2 == 0:
    ans = Decimal(distAB) / Decimal(2)
else:
    if (N-B) < A:
        ans = (N-B+1) + (Decimal(distAB-1)/Decimal(2))
    else:
        ans = A+1 + (Decimal(distAB-1)/Decimal(2))

print(int(ans))
if (a*b)//2 == 1:
  print('odd')
else:
  print('even')

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 == 1:
  print('Odd')
else:
  print('Even')
import itertools
N=int(input())
l=[]
#l:調査情報のリスト
M=max(item[2] for item in l)
for i in range(N):
  x,y,h=map(int,input().split())
  l.append([x,y,h])
s=list(itertools.product(range(0,101),repeat=2))
#s:中心座標の候補リスト
for A,B in itertools.combinations(range(N),2):
  #調査情報の全ての2つ組を用いて絞り込む
  if len(s)==1:
    break
  t=[]
  #t:新たな中心座標の候補リスト
  if l[A][2]<l[B][2]:
    A,B=B,A
  if l[A][2]>l[B][2]:
    #2地点の高さが異なる場合
    if l[B][2]==0:
      #B地点の高さが0ならB地点は中心から[Aの高さ]以上離れている
      gap=l[A][2]-l[B][2]
      for X,Y in s:
        if abs(X-l[A][0])+abs(Y-l[A][1])+gap<=abs(X-l[B][0])+abs(Y-l[B][1]):
          t.append((X,Y))
    else:
      #B地点の高さが0でなければA地点は中心から[Aの高さ-Bの高さ]だけ離れている
      gap=l[A][2]-l[B][2]
      for X,Y in s:
        if abs(X-l[A][0])+abs(Y-l[A][1])+gap==abs(X-l[B][0])+abs(Y-l[B][1]):
          t.append((X,Y))
  
  elif l[A][2]!=0:
    #2地点の高さが等しく0ではない場合
    for X,Y in s:
      if abs(X-l[A][0])+abs(Y-l[A][1])==abs(X-l[B][0])+abs(Y-l[B][1]):
        t.append((X,Y))
  else:
    #2地点の高さが等しく0の場合
    #2地点が中心ではない
    for X,Y in s:
      if abs(X-l[A][0])+abs(Y-l[A][1])>=M and abs(X-l[B][0])+abs(Y-l[B][1])>=M:
        t.append((X,Y))
  s=t[:]
#sの要素は唯一だと思いたい
a,b=s[0][0],s[0][1]
h=abs(a-l[0][0])+abs(b-l[0][1])+l[0][2]
print(a,b,h)


### FIXED CODE ###

import itertools
N=int(input())
l=[]
#l:調査情報のリスト
for i in range(N):
  x,y,h=map(int,input().split())
  l.append([x,y,h])
M=max(item[2] for item in l)#高さの最大値(暫定)
s=list(itertools.product(range(0,101),repeat=2))
#s:中心座標の候補リスト
for A,B in itertools.combinations(range(N),2):
  #調査情報の全ての2つ組を用いて絞り込む
  if len(s)==1:
    break
  t=[]
  #t:新たな中心座標の候補リスト
  if l[A][2]<l[B][2]:
    A,B=B,A
  if l[A][2]>l[B][2]:
    #2地点の高さが異なる場合
    if l[B][2]==0:
      #B地点の高さが0ならB地点は中心から[Aの高さ]以上離れている
      gap=l[A][2]-l[B][2]
      for X,Y in s:
        if abs(X-l[A][0])+abs(Y-l[A][1])+gap<=abs(X-l[B][0])+abs(Y-l[B][1]):
          t.append((X,Y))
    else:
      #B地点の高さが0でなければA地点は中心から[Aの高さ-Bの高さ]だけ離れている
      gap=l[A][2]-l[B][2]
      for X,Y in s:
        if abs(X-l[A][0])+abs(Y-l[A][1])+gap==abs(X-l[B][0])+abs(Y-l[B][1]):
          t.append((X,Y))
  
  elif l[A][2]!=0:
    #2地点の高さが等しく0ではない場合
    #2地点からM-[Aの高さ]以上離れた地点のみ残す
    for X,Y in s:
      MM=max(1,M-l[A][2])
      if abs(X-l[A][0])+abs(Y-l[A][1])==abs(X-l[B][0])+abs(Y-l[B][1]) and abs(X-l[A][0])+abs(Y-l[A][1])>=MM and abs(X-l[B][0])+abs(Y-l[B][1])>=MM:
        t.append((X,Y))
  else:
    #2地点の高さが等しく0の場合
    #2地点からM以上離れた地点のみ残す
    for X,Y in s:
      if abs(X-l[A][0])+abs(Y-l[A][1])>=M and abs(X-l[B][0])+abs(Y-l[B][1])>=M:
        t.append((X,Y))
  s=t[:]
#sの要素は唯一だと思いたい
a,b=s[0][0],s[0][1]
i=0
while l[i][2]==0:
  i+=1

h=abs(a-l[i][0])+abs(b-l[i][1])+l[i][2]
print(a,b,h)
import sys
from operator import itemgetter
input=sys.stdin.readline
n,x=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
b=list(zip(*a))
t=max(b[0])
a.sort(key=itemgetter(1),reverse=True)
ans=0
for i in range(n):
  if x<=0:
    print(ans)
    break
  if a[1][i]>=t:
    x-=a[1][i]
    ans+=1
  else:
    ans+=(x+t-1)//t
    x=0

### FIXED CODE ###

import sys
from operator import itemgetter
input=sys.stdin.readline
n,x=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
b=list(zip(*a))
t=max(b[0])
a.sort(key=itemgetter(1),reverse=True)
ans=0
for i in range(n):
  if a[i][1]>=t:
    x-=a[i][1]
    ans+=1
  if x<=0:
    print(ans)
    break
else:
  ans+=(x+t-1)//t
  x=0
  print(ans)
def main():
    N,C = [int(_n) for _n in input().split()]
    L = 100000
    table = [[0]*L for _ in range(C)]
    for i in range(N):
        s,t,c = [int(_n) for _n in input().split()]
        c -= 1
        s -= 1
        t -= 1
        table[c][s] += 1
        table[c][t+1] -= 1 
    for c in range(C):
        for j in range(L-1):
            table[c][j+1] += table[c][j]
    for i in range(C):
        for j in range(L):
            table[i][j] = min(1, table[i][j])
    for j in range(L):
        for c in range(C-1):
            table[c+1][j] += table[c][j]
    print(max(table[C-1]))
    # print(table)
    # print(table)
    # acc = [0] * len(times)
    # progs.sort(key = lambda x:x[2])



main()

### FIXED CODE ###

def main():
    N,C = [int(_n) for _n in input().split()]
    L = 100010
    table = [[0]*L for _ in range(C)]
    for i in range(N):
        s,t,c = [int(_n) for _n in input().split()]
        c -= 1
        s -= 1
        t -= 1
        table[c][s] += 1
        table[c][t+1] -= 1 
    for c in range(C):
        for j in range(L-1):
            table[c][j+1] += table[c][j]
    for i in range(C):
        for j in range(L):
            table[i][j] = min(1, table[i][j])
    for j in range(L):
        for c in range(C-1):
            table[c+1][j] += table[c][j]
    print(max(table[C-1]))
    # print(table)
    # print(table)
    # acc = [0] * len(times)
    # progs.sort(key = lambda x:x[2])



main()
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
cnt == 0
for i in range(n):
    if v[i] > c[i]:
        cnt += (v[i] - c[i])
    else:
        cnt += 0
print(cnt) 

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
cnt = 0
for i in range(n):
    if v[i] > c[i]:
        cnt += (v[i] - c[i])
print(cnt)
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def union(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.find(a), self.find(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.find(a) == self.find(b)

    def find(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.find(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.find(a)]

    def groups(self):
        find_buf = [self.find(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[find_buf[i]].append(i)
        return [r for r in result if r != []]

N, M = map(int,input().split())
uf = UnionFind(N)
setrecursionlimit(10**9+7)

for i in range(M):
    a,b = map(int,input().split())
    uf.union(a,b)

print(len(uf.groups())-1)

### FIXED CODE ###

from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def union(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.find(a), self.find(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.find(a) == self.find(b)

    def find(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.find(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.find(a)]

    def groups(self):
        find_buf = [self.find(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[find_buf[i]].append(i)
        return [r for r in result if r != []]

N, M = map(int,input().split())
uf = UnionFind(N)
setrecursionlimit(10**9+7)

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)

print(len(uf.groups())-1)
n=int(input())
s=[int(input()) for i in range(n)]
memo=[[0]*10000 for i in range(100)]
def dp(score, i):
    if i==n:
        if score%10==0:
            memo[i][score]=0
            return 0
        else:
            memo[i][score]=score
            return score
    if memo[i][score]>0:
        return memo[i][score]
    memo[i][score]=max(dp(score+s[i-1], i+1), dp(score, i+1))
    return memo[i][score]
print(dp(0,0))

### FIXED CODE ###

n=int(input())
s=[int(input()) for i in range(n)]
memo=[[-1]*20000 for i in range(200)]
def dp(score, i):
    if i==n:
        if score%10==0:
            memo[i][score]=0
            return 0
        else:
            memo[i][score]=score
            return score
    if memo[i][score]>=0:
        return memo[i][score]
    memo[i][score]=max(dp(score+s[i-1], i+1), dp(score, i+1))
    return memo[i][score]
print(dp(0,0))
import math
N = int(input())

a = 2 * N / math.gcd(2, N)

print(a)

### FIXED CODE ###

N = int(input())
if N%2==0:
    print(N)
elif N%2!=0:
    print(2*N)
import math
A,B = map(double,input().split())
print(int(A * B))

### FIXED CODE ###

import math
from decimal import Decimal
a, b = input().split()
a = int(a)
b = Decimal(b)
print(math.floor(a * b))
S = list(input())
ACGT_filter = ['A', 'C', 'G', 'T']

str_length = 0
str_lengths = []
for s in S:
    if s in ACGT_filter:
        print(s)
        str_length += 1
    else:
        str_lengths.append(str_length)
        str_length = 0

print(max(str_lengths))

### FIXED CODE ###

ACGT_filter = ['A', 'C', 'G', 'T']

ans = 0
now = 0
for s in input():
    if s in ACGT_filter:
        now += 1
    else:
        now = 0
    ans = max(now, ans)

print(ans)
l = input().split()
s = input()
 
n = int(l[0])
a = int(l[1])
b = int(l[2])
 
count = 0
countt = 0
for i in s:
    if i == 'a':
        if count < a+b:
            count = count + 1
            print('Yes')
        else:
            print('No')
    if i == 'b':
        if (count < a+b) and (countt < b):
            count = count + 1
            countt = countt + 1
            print('Yes')
        else:
            print('No')
    if i == 'c':
        print('No')

### FIXED CODE ###

s = input()

standard = 'CODEFESTIVAL2016'

count = 0
for i in range(16):
    if s[i] != standard[i]:
        count = count + 1
print(count)
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(b):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*b
    idx += b
print(ad + sum(a[idx:]))

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(min(b, n-idx)):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*min(b, n-idx)
    idx += min(b, n-idx)
print(ad + sum(a[idx:]))
import sys
from collections import defaultdict
from functools import lru_cache


g = None


@lru_cache(maxsize=100000)
def f(x):
    return max((f(y) + 1 for y in g[x]), default=0)


def resolve(in_):
    global g
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    return max(f(i) for i in range(n))


def main():
    ans = resolve(sys.stdin.buffer)
    print(ans.decode())


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict


g = None
memo = None


def f(x):
    if memo[x] == -1:
        ret = 0
        for y in g[x]:
            ret = max(ret, f(y) + 1)
        memo[x] = ret
    return memo[x]


def resolve(in_):
    global g, memo
    n, m = map(int, next(in_).split())
    _g = defaultdict(list)
    for line in in_:
        x, y = map(int, line.split())
        _g[x - 1].append(y - 1)
    g = _g
    memo = [-1] * 100000
    return max(f(i) for i in range(n))


def main():
    sys.setrecursionlimit(1000000)
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()
A, B = map(int, input().split())
if A >= 13:
  print(B)
elif A <= 12 and A >= 6:
  print(B/2)
eiif A < 6:
  print(0) 

### FIXED CODE ###

A, B = map(int, input().split())
if A >= 13:
	B = B
elif A <= 12 and A >= 6:
  B = B // 2
elif A < 6:
  B *= 0
print(B)
import bisect

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
for i in range(1,100):
    if 2**i>2*(10**9):
        break
    else:
        B.append(2**i)
B.append(2**(i+1))
ans=0
#print(B)
for i in range(N):
    X=bisect.bisect_left(B,A[N-1-i])
    if B[X]==A[N-1-i]:
        X+=1
    #print(X)
    if A[bisect.bisect_left(A,B[X]-A[N-1-i])]==B[X]-A[N-1-i]:
        ans+=1
        A[bisect.bisect_left(A,B[X]-A[N-1-i])]-=0.1
        A[N-1-i]-=0.1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
A.append(999999999999999)
B=[]
for i in range(1,35):
    B.append(2**i)
ans=0
for i in range(N):
    if A[N-1-i]==int(A[N-1-i]):
        for j in range(len(B)):
            if A[N-1-i]<B[j]:
                break
        if A[bisect.bisect_left(A,B[j]-A[N-1-i])]==B[j]-A[N-1-i]:
            if bisect.bisect_left(A,B[j]-A[N-1-i])<N-1-i:
                A[bisect.bisect_left(A,B[j]-A[N-1-i])]-=0.1
                A[N-1-i]+=0.1
                ans+=1
print(ans)