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

# ABC_129 C

def stairs(n, a):
    num_list = [i for i in range(n+1) if i not in a]
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in num_list:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]

    result = dp[n] % 1000000007

    print(result)


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

if __name__ == '__main__':
    stairs(n, a)

### FIXED CODE ###

# ABC_129 C

def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in num_list:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

    
n, m = list(map(int, input().split()))
a = set(int(input()) for _ in range(m))


if __name__ == '__main__':
    stairs(n, a)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [0]*q
pt = [k]*n
for i in range(q):
    a[i] = int(input())
    for j in range(n):
        if j != (a[i] - 1):
            pt[j] -= 1
for i in range(n):
    if pt[i] <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

#!/usr/bin/env python3
n,k,q = map(int,input().split())
a = [int(input())-1 for i in range(q)]
cnt = [0]*n
for question in a:
    cnt[question] += 1
#print(cnt)#点数は k-q+cnt > 0
for man in range(n):
    if cnt[man] > q - k: print("Yes")
    else: print("No")
### BUGGY CODE ###

n, m = map(int, input().split())
sum = 0
money = 0
A = list()
B = list()
for i in range(n):
    a, b = input().split()
    A.append(int(a))
    B.append(int(b))
for i in range(n):
    index = A.index(min(A))
    if(B[index] >= m - sum):
        money += A[index] * (m - sum)
        sum = m
        break
    else:
        sum += B[index]
        money += A[index]*B[index]
    del A[index]
    del B[index]
print(money)

### FIXED CODE ###

n, m = map(int, input().split())
sum = 0
money = 0
list_ab = list()
for i in range(n):
    list_ab.append(list(map(int, input().split())))
list_ab = sorted(list_ab)
for i in range(n):
    if(list_ab[i][1] >= m - sum):
        money += list_ab[i][0] * (m - sum)
        break
    else:
        sum += list_ab[i][1]
        money += list_ab[i][0]*list_ab[i][1]
print(money)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

n, m, s, t = map(int, input().split())
c = 10**15
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  q = []
  heappush(q, (0, s))

  while len(q):
    cost, cur = heappop(q)
    used = defaultdict(bool)

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

for i in range(n):
  ans = float("INF")
  for j in range(i+1, n+1):
    ans = min(ans, dyen[j]+dsnuuk[j])
  print(c-ans)

### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush

n, m, s, t = map(int, input().split())
c = 10**15
graph = defaultdict(list)
for _ in range(m):
  u, v, a, b = map(int, input().split())
  graph[u].append((v, a, b))
  graph[v].append((u, a, b))

dyen = defaultdict(lambda:float("INF"))
dsnuuk = defaultdict(lambda:float("INF"))
dyen[s] = 0
dsnuuk[t] = 0

def dijkstra(s, m):
  used = defaultdict(bool)
  q = []
  heappush(q, (0, s))

  while len(q):
    v = heappop(q)
    cost, cur = v[0], v[1]

    if used[v]:
      continue
    used[v]=True

    for to, a, b in graph[cur]:
      if m==0 and dyen[to]>cost+a:
        dyen[to] = cost+a
        heappush(q, (cost+a, to))
      elif m==1 and dsnuuk[to]>cost+b:
        dsnuuk[to] = cost+b
        heappush(q, (cost+b, to))

dijkstra(s, 0)
dijkstra(t, 1)

costs = [float("INF")]*(n+1)
min_ = float("INF")
for i in range(n, 0, -1):
  min_ = min(min_, dyen[i]+dsnuuk[i])
  costs[i] = min_

for i in range(1, n+1):
  print(c-costs[i])
### BUGGY CODE ###

N = int(input())
for i in range(int(N**0.5),N+1):
    if N % i == 0:
        print(N//i + i - 2)
        break

### FIXED CODE ###

N = int(input())
for i in range(int(N**0.5),0,-1):
    if N % i == 0:
        print(N//i + i - 2)
        break
### BUGGY CODE ###

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

for i in range(N):
        print(A.index(A_copy[i]) + 1, end=' ')

### FIXED CODE ###

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

B = [0 for i in range(N)]

for i in range(N):
  B[A[i] - 1] = i + 1
 
print(' '.join(map(str, B)))
### BUGGY CODE ###

N = int(input())
s = input()

result = 0

for l in range((N+1)//2, -1, -1):
    for start in range(N - 2*l + 1):
        if s[start:start+l] in s[start+l:]:
            result = l
            break
    if result > 0:
        break

print(result)


### FIXED CODE ###

import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))
### BUGGY CODE ###

import itertools

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [i for i in range(n)]

def add(k, x):
  while k <= n:
    data[k] += x
    k += k & -k
def get(k):
  s = 0
  while k:
    s += data[k]
    k -= k & -k
  return s
ans = 10 ** 18
for i in itertools.combinations(c,n//2):
  j = list(set(c)-set(i))
  even = sorted([(a[k],k+1) if k % 2 else (b[k],k+1) for k in i])
  odd = sorted([(b[k],k+1) if k % 2 else (a[k],k+1) for k in j])
  prev = -1
  A = []
  for x in range(n):
    Y,X = divmod(x,2)
    if X % 2:
      now0,now1 = even[Y][0],even[Y][1]
    else:
      now0,now1 = odd[Y][0],odd[Y][1]
    if prev > now0:
      break
    else:
      A.append(now1)
    prev = now0
  else:
    data = [0]*(n+1)
    tmp = 0
    for i,z in enumerate(A):
      tmp += (n-1-i) - get(z)
      add(z,1)
    ans = min(ans,tmp)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import itertools

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [i for i in range(n)]

def add(k, x):
  while k <= n:
    data[k] += x
    k += k & -k
def get(k):
  s = 0
  while k:
    s += data[k]
    k -= k & -k
  return s
ans = 10 ** 18
for i in itertools.combinations(c,n//2):
  j = list(set(c)-set(i))
  even = sorted([(a[k],k+1) if k % 2 else (b[k],k+1) for k in i])
  odd = sorted([(b[k],k+1) if k % 2 else (a[k],k+1) for k in j])
  prev = -1
  A = []
  for x in range(n):
    Y,X = divmod(x,2)
    if X % 2:
      now0,now1 = even[Y][0],even[Y][1]
    else:
      now0,now1 = odd[Y][0],odd[Y][1]
    if prev > now0:
      break
    else:
      A.append(now1)
    prev = now0
  else:
    data = [0]*(n+1)
    tmp = 0
    for i,z in enumerate(A):
      tmp += (n-1-i) - get(z)
      add(z,1)
    ans = min(ans,tmp)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

lim = 10**9+7
n=int(input())
A=[int(i) for i in input().split()]
binary = [bin(i)[2:].zfill(60)[::-1] for i in A]

ans=0
for i in range(60):
    l = [s[i] for s in binary]
    #print(i,l.count("0") * l.count("1"))
    ans = (ans+ ((l.count("0") * l.count("1"))% lim * 2**i )% lim)% lim
print(ans % lim)

### FIXED CODE ###

lim = 10**9+7
n=int(input())
A=[int(i) for i in input().split()]
binary = [bin(i)[2:].zfill(60)[::-1] for i in A]

ans=0
for i in range(60):
    l = [s[i] for s in binary]
    #print(i,l.count("0") * l.count("1"))
    ans = (ans+ ((l.count("0") * l.count("1"))% lim * 2**i )% lim)% lim
print(ans % lim)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
e = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


def dijkstra(s,cu):
    inf = 10**18
    d = [inf]*n
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]>d[v]+ud[cu]:
                d[u] = d[v] + ud[cu]
                heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n-1]+db[n-1]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i]+db[i])

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

import numpy as np


def atcoder_input():
    H, W = (int(i) for i in input().split())
    tmp = []

    for i in range(H):
        l = [j for j in input().split()]
        tmp.append(list(l[0]))
    tmp = np.array(tmp)

    A=(tmp=="#").astype(int)

    return A, H, W


def main():
    A, H, W = atcoder_input()

    old_x_where = list(np.where(A == 1)[0])
    old_y_where = list(np.where(A == 1)[1])

    counter = 0

    while np.min(A) == 0:
        counter += 1
        new_x_where = []
        new_y_where = []
        for i in range(4):
            if i == 0:
                tmp_x = list(np.clip(np.array(old_x_where) + 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            elif i == 1:
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) + 1, 0, H - 1))
            elif i == 2:
                tmp_x = list(np.clip(np.array(old_x_where) - 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            else:  # i=3
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) - 1, 0, H - 1))

            new_x_where.extend(tmp_x)
            new_y_where.extend(tmp_y)

        del_pos = np.array(np.where(A[new_y_where, new_x_where]==0)[0])
        new_y_where = list(np.array(new_y_where)[del_pos])
        new_x_where = list(np.array(new_x_where)[del_pos])

        A[new_y_where, new_x_where] = 1
        old_x_where = new_x_where
        old_y_where = new_y_where

    print(counter)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p - W)
    if h != H-1:
        q_list.append(p + W)
    if w != 0:
        q_list.append(p - 1)
    if w != W-1:
        q_list.append(p + 1)
    return q_list


queue = deque(black_cells)
d = [10000] * (H * W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	s = input()
	n = int(input())
	f = 0
	l = ""
	r = ""
	for i in range(n):
		q=input().split()
		if q[0] == "1":
			f ^= 1
		else:
			if (f == 0 and q[1] == "1") or (f == 1 and q[1] == "2"):
				l = l + q[2]
			else:
				r = r + q[2]
	if f == 0:
		ans = l[::-1] + s + r
	else:
		ans = r[::-1] + s[::-1] + l
	print(ans)


if __name__ == "__main__":
	main()


### FIXED CODE ###

s=input()
n=int(input())
f=0
l=""
r=""
for i in range(n):
	q=input().split()
	if q[0]=="1":
		f^=1
	else:
		if (f==0 and q[1]=="1") or (f==1 and q[1]=="2"):
			l=l+q[2]
		else:
			r=r+q[2]

if f==0:
	ans=l[::-1]+s+r
else:
	ans=r[::-1]+s[::-1]+l

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

from functools import reduce
import collections


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

l = {}
answer = 0
for aa in a:
    c = collections.Counter(prime_factorize(aa))
    for k in c.keys():
        if k in l:
            l[k] = max(c[k], l[k])
        else:
            l[k] = c[k]

for aa in a:
    ll = 1
    c = collections.Counter(prime_factorize(aa))
    for k in l.keys():
        if k in c:
            ll = ll * (k ** (l[k] - c[k]))
        else:
            ll = ll * (k ** l[k])
    answer += ll
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)


### FIXED CODE ###

# import math
# import fractions

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

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)
### BUGGY CODE ###

s = input()
s_list = list(s)
s_len = len(s)
count = 0
count_cur = 0
count_before = None
while(count != count_before):
  count_cur = 0
  for i in range(s_len-1):
    if s_list[i] == 'B' and s_list[i+1] == 'W':
      count_cur += 1
      s_list[i] = 'W'
      s_list[i+1] = 'B'
  count_before = count
  count += count_cur 

print(count)



### FIXED CODE ###

S = list(input())
W_i = [i for i,j in enumerate(S) if j == 'W']
W_n = S.count('W')
cur = 0
ans = 0
for i in W_i:
  ans += i-cur
  cur += 1
print(ans)
### BUGGY CODE ###

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

n = a[0]
k = a[1]

c = []
bfr = 0
aft = 0
for i in range(k-1, n):
    aft = 1
    for j in reversed(range(k)):
        aft *= b[i - j]
    if bfr != 0:
        if bfr < aft:
            c.append("Yes")
        else:
            c.append("No")
    bfr = aft
            
s_n = '\n'.join(c)
print(s_n)   

### FIXED CODE ###

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

n = a[0]
k = a[1]

c = []
bfr = 0
aft = 0
for i in range(k-1, n):
    if i != k-1:
        if b[i - k] < b[i]:
            c.append("Yes")
        else:
            c.append("No")
    
            
s_n = '\n'.join(c)
print(s_n)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  for l1 in range(N//l[1]+1):
    l2 = (N - l0*l[0] - l1*l[1])/l[2]
    if l2%1.0 == 0 and l2 >= 0:
      count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  n0 = N-l0*l[0]
  for l1 in range(n0//l[1]+1):
    l2 = n0 - l1*l[1]
    if l2%l[2] == 0 and l2 >= 0:
      count += 1
print(count)
### BUGGY CODE ###

import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a for a in A)
    print(b%MOD)
main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for r in [A.count(i) for i in range(1, N + 1)]:
    print(r)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
for i in range(1, N + 1):
    if c[i]:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

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

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

B = []
C = []
for _ in range(Q):
    B_i, C_i = map(int, input().split())
    
    B.append(B_i)
    C.append(C_i)

max_i = max(max(A), max(C))

A_N = [A.count(i) * i for i in range(max_i + 1)]

for i in range(Q):
    A_N[C[i]] += int(A_N[B[i]] / B[i]) * C[i]
    A_N[B[i]] = 0
    
    print(sum(A_N))



### FIXED CODE ###

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

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

B = []
C = []
for _ in range(Q):
    B_i, C_i = map(int, input().split())
    
    B.append(B_i)
    C.append(C_i)

max_i = max(max(A), max(C))

A_N = [0 for _ in range(max_i + 1)]
sum_i = 0

for a in A:
    A_N[a] += a
    sum_i += a

for i in range(Q):
    diff_replace = int(A_N[B[i]] / B[i]) * C[i]
    sum_i += diff_replace - A_N[B[i]]
    
    A_N[C[i]] += diff_replace
    A_N[B[i]] = 0
    
    print(sum_i)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

ans = 1
for i in range(n):
    
    ans *=a[i]
    
if ans >10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

ans = 1
for i in range(n):
    ans *=a[i]
    if ans>10**18:
        ans = -1
        break

if 0 in a:
    ans = 0
        
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from itertools import permutations

  X,Y,Z,K = map(int,input().split())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort(reverse = True)
  B.sort(reverse = True)
  C.sort(reverse = True)
  res = []
  for a in A[:K]:
    for b in B[:K]:
      for c in C[:K]:
        res.append(a+b+c)
  res.sort(reverse = True)
  print("\n".join(list(map(str,res[:K]))))

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline

  X,Y,Z,K = map(int,input().split())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort(reverse = True)
  B.sort(reverse = True)
  C.sort(reverse = True)
  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:min(K, len(AB))] for c in C]
  res.sort(reverse = True)
  print("\n".join(list(map(str,res[:K]))))

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

n, m, q = map(int, input().split())
Arr = []
for i in range(n+1):
  Arr.append([0] * (n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

for i in range(q):
  left, right = map(int, input().split())
  train_num = 0
  for j in range(left, right+1):
    for k in range(left, right+1):
      train_num += Arr[j][k]
  print(train_num)

### FIXED CODE ###

n, m, q = map(int, input().split())
Arr = []
for i in range(n+1):
  Arr.append([0] * (n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

B = []
for i in range(n+1):
  B_line = [0]
  for j in range(1, n+1):
    B_line.append(B_line[-1] + Arr[i][j])
  B.append(B_line)
#print(B)
  
for x in range(q):
  left, right = map(int, input().split())
  train_num = 0
  for i in range(left, right+1):
    train_num += B[i][right] - B[i][left-1]
  print(train_num)
### BUGGY CODE ###

from collections import defaultdict

N, M = map(int, input().split())
Hs = list(map(int, input().split()))
ABs = []
for _ in range(M):
    ABs.append(tuple(map(int, input().split())))

ans = 0
edges = defaultdict(list)
for u, v in ABs:
    if u > v:
        u, v = v, u
    if v not in edges[u]:
        edges[u].append(v)
        edges[v].append(u)

for e, neighbors in edges.items():
    heights = [Hs[neighbor - 1] for neighbor in neighbors]
    is_good = all(list(map(lambda x: Hs[e - 1] > x, heights)))
    if is_good:
        ans += 1

print(ans + len(set(range(1, N + 1)) - set(edges.keys())))


### FIXED CODE ###

from collections import defaultdict

N, M = map(int, input().split())
Hs = list(map(int, input().split()))
ABs = []
for _ in range(M):
    ABs.append(tuple(map(int, input().split())))

ans = 0
edges = defaultdict(list)
for u, v in ABs:
    if u > v:
        u, v = v, u
    if v not in edges[u]:
        edges[u].append(v)
        edges[v].append(u)

for e, neighbors in edges.items():
    heights = [Hs[neighbor - 1] for neighbor in neighbors]
    is_good = all(list(map(lambda x: Hs[e - 1] > x, heights)))
    if is_good:
        ans += 1

print(ans + len(set(range(1, N + 1)) - set(edges.keys())))
### BUGGY CODE ###

import heapq

h = []
h2 = []
N, M = [int(i) for i in input().split()]
count = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in count.items():
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    heapq.heappush(h2, (C, B))

for i in range(M - 1, -1, -1):
    C, B = h2[i]
    while B > 0:
        if h[0][0] >= C:
            break
        m = h[0][0]
        mc = h[0][1]
        if mc > B:
            heapq.heappush(h, (C, B))
            h[0] = (m, mc - B)
        else:
            heapq.heappop(h)
            heapq.heappush(h, (C, mc))
        B -= mc
print(sum([i[0] * i[1] for i in h]))



### FIXED CODE ###

import heapq

h = []
h2 = []
N, M = [int(i) for i in input().split()]
count = dict()
count2 = dict()
for i in input().split():
    if not count.get(i):
        count[i] = 0
    count[i] += 1
for k, v in count.items():
    heapq.heappush(h, (int(k), v))

for _ in range(M):
    B, C = [int(i) for i in input().split()]
    if not count2.get(C):
        count2[C] = 0
    count2[C] += B
for k, v in count2.items():
    heapq.heappush(h2, (-k, v))
while len(h2) > 0:
    C, B = heapq.heappop(h2)
    C = -C
    while B > 0:
        if h[0][0] >= C:
            break
        m = h[0][0]
        mc = h[0][1]
        if mc > B:
            heapq.heappush(h, (C, B))
            h[0] = (m, mc - B)
        else:
            heapq.heappop(h)
            heapq.heappush(h, (C, mc))
        B -= mc
print(sum([i[0] * i[1] for i in h]))