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

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a // gcd(lm,a)

ans = 0
for i in range(N):
    ans += ( lm//A[i] )
    ans %= Mod

print(ans)

### FIXED CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a//gcd(lm,a)

ans = 0
for i in range(N):
    ans += lm//A[i]
ans %= Mod

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

N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


res = [0] * (N + 1)
for i in range(1, N + 1):
    queue = [i]
    seen = {i}
    while queue:
        new = []
        for cur in queue:
            if i != cur and cur not in graph[i] and cur not in banned[i]:
                res[i] += 1
            for nxt in graph[cur]:
                if nxt not in seen:
                    seen.add(nxt)
                    new.append(nxt)
        queue = new
print(*res[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)

# BFS
group = {i: -1 for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
for i in range(1, N + 1):
    if group[i] >= 0:
        continue
    queue = [i]
    group[i] = i
    count[i] += 1
    while queue:
        new = []
        for cur in queue:
            for nxt in graph[cur]:
                if group[nxt] == -1:
                    group[nxt] = group[cur]
                    count[group[nxt]] += 1
                    new.append(nxt)
        queue = new

res = [0] * N
# Remove itself
for i in range(N):
    res[i] = count[group[i + 1]] - 1

# Remove friends and blocked users
for i in range(N):
    for j in banned[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
    for j in graph[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
print(*res)
### BUGGY CODE ###

n=int(input())
list=[int(input()) for i in range(n)]
max = 0
for i in range(n):
    if(i == 0):
        max = list[1]
    else:
        max = list[0]
    count = 0
    for c in list:
        if(max < c and i != count):
            max = c
        count += 1
    print(max)


### FIXED CODE ###

import copy
n=int(input())
list=[int(input()) for i in range(n)]
temp_list = copy.copy(list)
temp_list.sort(reverse=True)

max = 0
for c in list:
    if(c == temp_list[0]):
        print(temp_list[1])
    else:
        print(temp_list[0])
### BUGGY CODE ###

#D
a, b, n = map(int, input().split())
m = 0
for i in range(1,n+1):
    tmp = (a * i // b) - (a *( i // b))
    if m < tmp:
        m = tmp
print(m)

### FIXED CODE ###

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

if n < b:
    print(a * n // b)
else:
    print(a * (b - 1) // b)
### BUGGY CODE ###

N=int(input())
AN=map(int, input().split())
BN=[0 for i in range(N)]
for i in AN:
    BN[i-1] += 1

for K in range(1, N+1):
    b = BN[:]
    c = 0
    while True:
        if len(b) < K:
            break
        b.sort(reverse=True)
        c += b[K-1]
        for i in range(K):
            b[i] -= b[K-1]
        b.pop(K-1)
    print (c)

### FIXED CODE ###

N=int(raw_input())
AN=map(int, raw_input().split())

BN=[0 for i in xrange(N)]
for i in AN:
    BN[i-1] += 1
BN.sort()

LN = [0 for i in xrange(N)]
s = 0
j = 0
try:
    for X in xrange(1, N+1):
        while j<N and  BN[j] < X:
            s += BN[j]
            j += 1
        LN[X-1] = (s + X*(N - j)) / X
except IndexError:
    pass

KN = [0 for i in xrange(N)]
for i in xrange(len(LN)):
    KN[LN[i]-1] = i+1

for i in xrange(len(KN)-2, -1, -1):
    if KN[i] == 0:
        KN[i] = KN[i+1]

for i in KN:
    print (str(i))
### BUGGY CODE ###

import sys
import re
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


def main():
    S = SI()
    ans = 0
    now = 0
    while(1):
        now = S.find("ABC")
        if now == -1:
            break
        ans += 1
        i = 1
        aa = 0
        while(S[now-i] == 'A' and now-i >= 0):
            ans += 1
            i += 1
            aa += 1
        # S = S[a+3:]
        bc = 0
        now += 3
        while(S[now:now+2] == "BC"):
            ans += 1
            now += 2
            bc += 1
        ans += aa*bc
        S = "A"*(aa+1) + S[now:]
    print(ans)


main()


### FIXED CODE ###

import sys
import re
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


def main():
    S = SI()
    ans = 0
    S = S.replace("A", "0")
    S = S.replace("BC", "1")
    a = 0
    b = 0
    for s in S:
        if s == "0":
            a += 1
        elif s == "1":
            ans += a
            b = 1
        else:
            a = 0
    print(ans)


main()
### BUGGY CODE ###

from heapq import heapify, heappush, heappop


(N, M), *AB = [list(map(int, s.split())) for s in open(0)]
A = AB[0]
heapify(A)
for b, c in AB[1:]:
    while b > 0 and c > A[0]:
        a = heappop(A)
        heappush(A, c)
        b -= 1
print(sum(A))

### FIXED CODE ###

(N, M), *AB = [list(map(int, s.split())) for s in open(0)]
A = sorted(AB[0])
D = []
for b, c in sorted(AB[1:], key=lambda x: (-x[1], x[0])):
    D.extend([c] * b)
    if len(D) >= N:
        D = D[:N]
        break
D = D[::-1]
for i in range(N):
    if not D or D[-1] <= A[i]:
        break
    A[i] = D.pop()

print(sum(A))
### BUGGY CODE ###

import functools
import fractions


def resolve():
	n,x=map(int,input().split())
	x_list=list(map(int,input().split()))
	x_list.append(x)
	a=[abs(i-j) for i in x_list for j in x_list if i!=j]
	print(functools.reduce(fractions.gcd,a))

resolve()

### FIXED CODE ###

import functools
import fractions

def resolve():
	n,x=map(int,input().split())
	x_list=list(map(int,input().split()))
	x_list.append(x)
	x_list.sort()
	a=[abs(x_list[i]-x_list[i+1]) for i in range(n)]
	print(functools.reduce(fractions.gcd,a))
resolve()
### BUGGY CODE ###

from itertools import combinations
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

ans = 10**9
for v in combinations(H, K):
    diff = max(v) - min(v)
    if diff < ans:
        ans = diff
    
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)

m = []
for i in range(N-K+1):
    m.append(h[i+K-1] - h[i])
print(min(m))
### BUGGY CODE ###

import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = [[None] for _ in range(N * 2)]
    X = [0] * (N * 2)
    for i in range(N):
        x, h = [int(x) for x in input().split()]
        XH[i * 2] = [x, h, float("inf")]
        XH[i * 2 + 1] = [x + 2 * D + 1, float("inf"), 0]
        X[i * 2] = x
        X[i * 2 + 1] = x + 2 * D + 1

    X.sort()
    XH.sort(key=itemgetter(0, 2))

    ans = 0
    ruiseki = 0

    for x, h, r in XH:
        if h != float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == float("inf"):
                    XH[nx][2] -= tmpruiseki
                else:
                    XH[nx + 1][2] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += r

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    R = [0] * (N * 2)
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append((x, h))
        XH.append((x + 2 * D + 1, -float("inf")))
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 1))

    ans = 0
    ruiseki = 0

    for i in range(N * 2):
        x, h = XH[i]
        if h != -float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == -float("inf"):
                    R[nx] -= tmpruiseki
                else:
                    R[nx + 1] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += R[i]

    print(ans)


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

n,m = map(int,input().split())

kyotu_s = {k for k in range(1,n+1)}

for i in range(m):
    l,r = map(int,input().split())
    s = {j for j in range(l,r+1)}
    kyotu_s = s & kyotu_s

print(len(kyotu_s))

### FIXED CODE ###

n,m = map(int,input().split())

min_i = 1
max_i = n

for i in range(m):
    l,r = map(int,input().split())
    min_i = max(min_i,l)
    max_i = min(max_i,r)

if max_i-min_i>=0:
    print(max_i-min_i+1)
else:
    print(0)
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    s = input()
    ans = 0
    r_cnt = s.count('R')
    g_cnt = s.count('G')
    g_cnt = s.count('G')

    for i in range(n):
        for j in range(1, n - i, 1):
            if s[i] != s[i+j]:
                for x in ('R', 'G', 'B'):
                    if x not in (s[i], s[i+j]):
                        tmp = x
                if i+2*j < n and s[i+2*j] == tmp:
                    ans += s[i+j+1:].count(tmp) - 1
                else:
                    ans += s[i+j+1:].count(tmp)

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    s = input()
    ans = s.count('R') * s.count('G') * s.count('B')

    for i in range(n):
        for j in range(1, (n - 1)//2 + 1, 1):
            if i + 2 * j < n:
                if s[i] != s[i + j] and s[i] != s[i + 2 * j] and s[i + j] != s[i + 2 * j]:
                    ans -= 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
ans = sum(a)
for i in range(q):
    bi,ci = map(int, input().split())
    b.append(bi)
    c.append(ci)
for i in range(q):
    ans += a.count(b[i]) * (c[i]-b[i])
    for j in range(a.count(b[i])):
        a.append(c[i])
    a = [j for j in a if j != b[i]]
    print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
s = []

ans = sum(a)
s = Counter(a)
for i in range(q):
    bi,ci = map(int, input().split())
    b.append(bi)
    c.append(ci)
for i in range(q):
    ans += s[b[i]] * (c[i]-b[i])
    s[c[i]] += s[b[i]]
    s[b[i]] = 0
    print(ans)
### BUGGY CODE ###

N=int(input())
ans=1
for i in range(1,N+1):
    ans=ans*i
print(ans%(10**9+7))

### FIXED CODE ###

N=int(input())
ans=1
for i in range(1,N+1):
    ans=ans*i
    ans=ans%(10**9+7)

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

from collections import Counter

s = input()[::-1]
n = len(s)
counts = [0] * 2019
counts[0] = 1
current = 0
d = 0

for c in s:
    current += int(c) * 10**d
    d += 1
    current %= 2019
    counts[current] += 1

ans = 0
for i, count in enumerate(counts):
    if count > 1:
        # print(i)
        ans += count * (count-1) //2
print(ans)


# res = [int(s[a:])%2019 for a in range(n)]
# res.append(0)

# ans = 0
# # count = Counter(res)
# # for i in range(2019):
# #     ans += (count[i] * (count[i] - 1)) // 2
# print(ans)



### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

from sys import stdin
input = stdin.readline
(R,C,K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

grids = [[0]*C for _ in range(R)]

for r,c,v in rcv:
    grids[r-1][c-1] = v

from collections import defaultdict
dp = defaultdict(int)

for r in range(R):
    for c in range(C):
        tmp = value = grids[r][c]
        for i in range(1,4):
            if c:
                tmp = max(tmp, dp[r,c-1,i])
                if i > 1:
                    tmp = max(tmp, dp[r,c-1,i-1] + value)
            if r and i == 1:
                tmp = max(tmp, dp[r-1,c,3] + value)
            dp[r,c,i] = tmp

print(dp[R-1,C-1,3])

### FIXED CODE ###

# from sys import stdin
# input = stdin.readline
(R,C,K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
 
grids = [[0]*C for _ in range(R)]
 
for r,c,v in rcv:
    grids[r-1][c-1] = v
 
dp = [0] * C

for r in range(R):
#     print(dp)
    ndp = [0] * C
    elm = [0] * 4
    for c in range(C):
        elm[0] = max(elm[0], dp[c])
        value = grids[r][c]
        if value:
            nelm = [0] * 4
            nelm[0] = elm[0]
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            for i in range(3)[::-1]:
                nelm[i + 1] = max(elm[i + 1], elm[i] + value)
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            elm = nelm
        ndp[c] = max(elm)
    dp = ndp
 

print(dp[-1])
### BUGGY CODE ###

MOD = 10**9+7
n = input()
a = list(map(int, input().split()))
ans = 0
for i, ai in enumerate(a):
  if i == len(a)-1:
    continue
  sum_aj = sum(a[i+1:])
  ans += ((ai%MOD)*(sum_aj%MOD))%MOD

print(ans%MOD)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
n = input()
a = list(map(int, input().split()))
ans = 0
cum_a = np.cumsum(a[::-1])
cum_a = cum_a[::-1]
for i, ai in enumerate(a):
  if i == len(a)-1:
    continue
  sum_aj = cum_a[i+1]
  ans += ((ai%MOD)*(sum_aj%MOD))%MOD

print(ans%MOD)
### BUGGY CODE ###

S, Q = map(int, input().split())
S = input()
qn = [list(map(int, input().split())) for _ in range(Q)]
for q in qn:
    print(S.count("AC", q[0]-1, q[1]))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
qn = [list(map(int, input().split())) for _ in range(Q)]
S = "0" + S
cnt = []
cnt.append(0)
for i in range(1, N+1):
    if (S[i-1:i+1] == "AC"):
        cnt.append(cnt[i-1] + 1)
    else:
        cnt.append(cnt[i-1])
for q in qn:
    ans = cnt[q[1]] - cnt[q[0]-1]
    if S[q[0]-1:q[0]+1] == "AC":
        ans -= 1
    print(ans)
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans = ans*A[i]

if ans>1e18:
    ans = -1

print(ans)


### FIXED CODE ###

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

A.sort()
ans = 1

if A[0] == 0:
    ans = 0
else:
    for i in range(N):
        ans = ans * A[N-1-i]
        if ans > 10**18:
            ans = -1
            break

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

#!python3

import heapq


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]


def solve(link, w):
    l = [None] * N
    visit = [False] * N
    visit_n = 0
    # cost, len, node
    hq = [(0, -1, 0)]
    while hq:
        if visit_n == N:
            break
        c, n, v = hq.pop()
        if visit[v] :
            continue
        visit[v] = True
        visit_n += 1
        l[v] = abs(n)
        for x in link[v]:
            if not visit[x]:
                heapq.heappush(hq, (c + 1, n + w[v][x], x))

    return l


def main():
    link = [[] for _ in range(N)]
    w = [[0] * N for _ in range(N)]
    for u, v in uv:
        u -= 1
        v -= 1
        link[u].append(v)
        link[v].append(u)
        if A[u] < A[v]:
            w[u][v] = -1
        if A[v] < A[u]:
            w[v][u] = -1
    
    l = solve(link, w)
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for u, v in uv:
    link[u].append(v)
    link[v].append(u)


def dfs(l, dp, pre, v):
    # LIS
    idx = np.searchsorted(dp, A[v - 1])
    l[v] = max(idx, l[pre])
    bef = dp[idx]
    dp[idx] = A[v - 1]
    
    for x in link[v]:
        if x != pre:
            dfs(l, dp, v, x)

    dp[idx] = bef


def main():
    l = [0] * (N + 1)
    dp = np.full(N + 1, INF)
    dp[0] = 0
    dfs(l, dp, 0, 1)
    for ans in l[1:]:
        print(ans)


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

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

s=input()+'0'
X=[0]*(len(s)+1)
for i in range(len(s)-1):
    if s[i]=='A' and s[i+1]=='C':
        X[i+1]+=1
Y=[]
for i in range(n):
    Y.append(sum(X[:i+1]))

for i in range(q):
    l,r=map(int,input().split())
    print(Y[r-1]-Y[l-1])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()+'Z'
A=[0]*(n+1)
cnt=0
for i in range(n):
    A[i]=cnt
    if s[i]=='A' and s[i+1]=='C':
        cnt+=1
ANS=[]
for i in range(q):
    l,r=map(int,input().split())
    ANS.append(A[r-1]-A[l-1])
for ans in ANS:
    print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [S[i:i+2] == "AC" for i in range(N)]
AC_csum = np.cumsum(is_AC)

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
 

if n==1:
    print(p)
else:
    for i in range(round((p**(1/n)+1)),0,-1):        
        if p%i==0:
            if p%(i**2)==0:
                if p%(i**n)==0:
                    print(i)
                    break
 

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
 
if N >= 45:
  print(ans)
elif N == 1:
  print(P)
  
 
  
else:
  i = 1
  while(i**N <= P):
    if P % (i**N) == 0:
      ans = i
    i += 1
  print(ans)
### BUGGY CODE ###

A, B, C, D = [int(i) for i in input().split()]
 
while A or C > 0:
  A -= D
  C -= B
 
if A >= C:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

A, B, C, D = [int(i) for i in input().split()]
 
while A or C > 0:
  C -= B
  if C<=0:
    print('Yes')
    break
  A -= D
  if A<= 0:
    print('No')
    break
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
x=[0]*len(a)

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      x[i]+=1
      continue
print(x.count(0))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
c=Counter(a)
s=list(set(a))
p=[True]*(10**6+1)

for x in s:
    t=x*2
    while t<=10**6:
        p[t]=False
        t+=x
ans=0
for x in a:
    if c[x]==1 and p[x]==True:
        ans+=1
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for n in range(N):
    w, v = map(int, input().split())

    for i in range(min(W, W-w), -1, -1):
        if dp[i] != -1:
            dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))


### FIXED CODE ###

N, W = map(int, input().split())
dp = [-1] * (W+1)
dp[0] = 0

for n in range(N):
    w, v = map(int, input().split())

    for i in range(min(W, W-w), -1, -1):
        if dp[i] != -1:
            dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))
### BUGGY CODE ###

from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for mx,Mx in combinations(X,2):
	for my,My in combinations(Y,2):
		if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
			ans=min(ans,(Mx-mx)*(My-my))
print(ans)

### FIXED CODE ###

n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)
### BUGGY CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

MAP=[["." for _ in range(w)] for _ in range(h)]
H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    MAP[i][j]="#"
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)