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

from math import gcd


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        if n % b == 0:
            fct.append(b)
        while n % b == 0:
            n //= b
        b = b + 1
    if n > 1:
        fct.append(n)
    return set(fct)


n = int(input())
a = list(map(int, input().split()))
b = a[0]

new_a = list(map(factorize, a))
#print(new_a)
wa = new_a[0]
cnt = 0
flag = 0
for i in range(1, n):
    b = gcd(b, a[i])
    if len(wa & new_a[i]) > 0 and flag == 0:
        flag = 1
        #print(wa, new_a[i])
    wa = wa | new_a[i]
if b != 1:
    print("not coprime")
    exit()
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

# for i in range(1, n):
#     b = gcd(b, a[i])
#     if b == 1:
#         break
# else:
#     print("not coprime")
#     exit()
#
# new_a = list(map(factorize, a))
# wa = new_a[0]
# cnt = 0
# flag = 0
# for i in range(1, n):
#     if len(wa & new_a[i]) > 0 and flag == 0:
#         flag = 1
#         break
#     wa = wa | new_a[i]
#
# if flag:
#     print("setwise coprime")
# else:
#     print("pairwise coprime")



### FIXED CODE ###

import math


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 set(a)


n = int(input())
a = list(map(int, input().split()))
num = a[0]
for i in range(1, n):
    num = math.gcd(num, a[i])
if num != 1:
    print("not coprime")
    exit()
prime_memo = {}
for i in range(n):
    prime_number = prime_factorize(a[i])
    for num in prime_number:
        if num not in prime_memo.keys():
            prime_memo[num] = 1
        else:
            print("setwise coprime")
            exit()
print("pairwise coprime")
### BUGGY CODE ###

N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    if i == 1:
        dp[i] = abs(inputs[i] - inputs[i-1])
    else:
        tmp = 10 ** 9
        start = max(0, i-K)
        dp[i] = min([dp[j] + abs(inputs[j] - inputs[i]) for j in range(start, i)])

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

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

N = int(input())
S = str(input())

l = []
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      s = S[i]+S[j]+S[k]
      l.append(s)

l = set(l)
ans = len(l)
print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())
R = S[::-1]

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  left = -1
  if z[2] in R:
    r = R.index(z[2]) + 1
    right = N-r
  else:
    continue
  if z[0] in S:
    left = S.index(z[0]) + 1
  else:
    continue
  if z[1] in S[left:right]:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)
### BUGGY CODE ###

n = int(input())
num = [int(x) for x in input().split()]
a = 1
max = 10**18

for i in num:
  a *= i
  
a = -1 if a > max else a
print(a)

### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]

if 0 in l:
    r=0
else:
    r = 1
    for x in range(n):
        r = r * l[x]
        if r > 10**18:
            r=-1
            break
  
print(r)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
 
XOR=0
for a in A:
    XOR^=a

for i in range(N):
    A[i] &=~XOR

USED=[0]*N

for bi in range(60,-1,-1):
    for i in range(N):
        if USED[i]==0 and A[i] & (1<<bi)!=0:
            USED[i]=1
            useind=i
            break
    else:
        continue
    
    for i in range(N):
        if i==useind:
            continue
        if A[i] & (1<<bi)!=0:
            A[i]^=A[useind]

ANS=0
for a in A:
    ANS^=a

print(2*ANS+XOR)




### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
 
XOR=0
for a in A:
    XOR^=a
 
for i in range(N):
    A[i] &=~XOR
    
USED=[0]*N
 
for bi in range(60,-1,-1):
    for i in range(N):
        if USED[i]==0 and A[i] & (1<<bi)!=0:
            USED[i]=1
            useind=i
            break
    else:
        continue
 
    for i in range(N):
        if i==useind:
            continue
        if A[i] & (1<<bi)!=0:
            A[i]^=A[useind]
            
ANS=0
for a in A:
    ANS^=a
 
print(2*ANS+XOR)
### BUGGY CODE ###

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

for i in range(N):
    s = 0
    a = 0
    for j, b in enumerate(A):
        if i == j:
            continue
        s += abs(a - b)
        a = b
    s += abs(a)
    print(s)


### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]


s = 0
for i in range(1, N+2):
    x = abs(A[i-1] - A[i])
    s += x

for i in range(1, N+1):
    x = abs(A[i-1] - A[i])
    y = abs(A[i] - A[i+1])
    z = abs(A[i-1] - A[i+1])
    print(s - x - y + z)
### BUGGY CODE ###

# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input()[:-1])
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        ai=a[i]
        gamei=game[i]
        j = ai[0]
        pre = gamei[j]
        for gi in range(1, n - 1):
            j = ai[gi]
            to[pre].append(gamei[j])
            pre = gamei[j]
#    print(to)

    ans=0
    for i in range(all_game):
        tmp=dfs(i)
        if tmp == -1:
            print(-1)
            exit()
        if tmp>ans:
            ans=tmp
#    print(dis)
    print(ans)

main()


### FIXED CODE ###

# YouTube1

def main():
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
    #    print(a)
    gam = []  # １日のgames
    # 初期化
    for i in range(n):
        ii = a[i][-1]
        if ii < i: continue
        if a[ii][-1] == i:
            gam.append([i, ii])
    days = 0
    fin = [False] * n
    fin_cnt = 0
    #    print(gam)
    while 1:
        days += 1
        pla = []  # 今日試合があったplayers
        for i, ii in gam:
            a[i].pop()
            a[ii].pop()
            pla.append(i)
            pla.append(ii)
        gam = []
        dec = set()
        for i in pla:
            if fin[i]: continue
            if not a[i]:
                fin[i] = True
                fin_cnt += 1
                if fin_cnt == n:
                    print(days)
                    exit()
                continue
            if i in dec: continue
            ii = a[i][-1]
            if a[ii][-1] == i:
                gam.append([i, ii])
                dec.add(ii)
        if not gam:
            print(-1)
            exit()

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
digit = [0] * 60
for a in A:
  binary = bin(a)[-1:1:-1]
  for j in range(len(binary)):
    digit[j] += int(binary[j])
ans = 0
mod = 10**9+7
for i in range(60):
  ans += digit[i] * (N - digit[i]) * pow(2, i, mod)
  ans %= mod
print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)
ans = 0
mod = 10**9+7
i = 1
while i < (1 << 60):
    count = np.count_nonzero(A & i)
    ans += count * (N-count) * i
    ans %= mod
    i <<= 1
print(ans)
### BUGGY CODE ###

from math import ceil, floor

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

A.sort(reverse=False)
F.sort(reverse=True)

if sum(A) <= K:
    print(0)
else:
    st = 0
    ed = 10 ** 12
    md = ceil((st + ed) / 2)
    while True:
        if sum([max(a - floor(md / f), 0) for (a, f) in zip(A, F)]) <= K:
            ed = md
        else:
            st = md
        md = ceil((st + ed) / 2)

        if md == ed:
            break

    print(md)


### FIXED CODE ###

import numpy as np
from math import ceil

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F.sort()

if np.sum(A) <= K:
    print(0)
else:
    st = 0
    ed = 10 ** 12
    md = ceil((st + ed) / 2)
    while True:
        if np.sum(A - np.minimum(A, md // F[::-1])) <= K:
            ed = md
        else:
            st = md
        md = ceil((st + ed) / 2)

        if md == ed:
            break

    print(md)
### BUGGY CODE ###

N,W = map(int, input().split())
w,v = [0]*N, [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
    
dp = [0]*(W+1) 
for i in range(N):
    for j in reversed(range(W+1)):
        if j-w[i]<0:
            dp[j] = dp[j]
        else:
            dp[j] = max(dp[j],
                        dp[j-w[i]] + v[i])
    # print(dp)
print(dp[W])

### FIXED CODE ###

N,W = map(int, input().split())
w,v = [0]*N, [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
    
dp = [0]*(W+1) 
for i in range(N):
    for j in reversed(range(W+1)):
        if j-w[i]<0:
            dp[j] = dp[j]
        else:
            dp[j] = max(dp[j],
                        dp[j-w[i]] + v[i])
    # print(dp)
print(dp[W])
### BUGGY CODE ###

# Not using k-d tree.

import sys
import bisect
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    a = []
    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()

    for i in a:
        print(i)
    print('')

### FIXED CODE ###

import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
DP = [INF]*N
DP[0] = 0
DP[1] = abs(h[1]-h[0])
for i in range(2,N):
    DP[i] = min(DP[i-j] + abs(h[i-j]-h[i]) for j in range(1,min(K,i)+1))
print(DP[-1])

### FIXED CODE ###


def frog2(H,N,K):
    #print(H)
    DP = [10**10]*N
    #DP = [0]*N
    DP[0] = 0
    DP[1] = abs(H[1]-H[0])
    for i in range(2,N):
        for j in range(1,K+1):
            DP[i] = chmin(DP[i],DP[i-j]+abs(H[i]-H[i-j]))
    return DP[-1]

def chmin(a,b):
    if a < b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,K = map(int,input().split())
    H = list(map(int,input().split()))
    ans = frog2(H,N,K)
    print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

extend = A.extend
[extend([BC[i][1]] * BC[i][0]) for i in range(m)]

A.sort(reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

N=int(input())
A = list(map(int, input().split()))
ans=1
for i in range(N):
    ans*=A[i]
    
if ans>10**18:
    ans=-1
print(ans)

### FIXED CODE ###

import numpy as np
import math
import functools
import operator
N=int(input())
A = list(map(int, input().split()))
#AA=A.sort()
if A.count(0)>0:
    ans=0
elif N>30 and A.count(1)<10:
    ans=-1
    
else:
    ans=functools.reduce(operator.mul, A)
if ans>10**18 :
    ans=-1
print(ans)
### BUGGY CODE ###

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

nm_list = [bin(x)[2:][::-1] for x in nums]

def syakutori():
    ans = 0
    bits = [0]*21
    r = 0
    l = 0
    flag = True
    #尺取り法をする
    while((l < len(nums)) or (not flag)):
        if not flag:
            #print("a", l, r, bits)
            for i, b in enumerate(nm_list[r]):
                bits[i] -= int(b)
            r += 1
            flag = max(bits) <= 1
            if flag:
                ans += (l - r)

        #rを伸ばす(ついでに数え上げる)
        else:
            #print("ans", l, r, bits)
            for i, b in enumerate(nm_list[l]):
                bits[i] += int(b)
            flag = max(bits) <= 1
            l += 1
            if flag:
                ans += (l - r)

    return ans


print(syakutori())


### FIXED CODE ###

import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    lis = getList()
    xo, su = 0, 0
    ans = 0
    l, r = 0, 0
    forward = True
    while True:
        # print(l, r, ans, xo, su)
        if r == n:
            print(ans)
            return
        if forward:
            xo = xo^lis[r]
            su += lis[r]
            if xo == su:

                ans += r - l + 1
                r += 1
            else:
                forward = False
        else:
            xo = xo^lis[l]
            su -= lis[l]
            if xo == su:
                forward = True
                ans += r - l
                r += 1
                l += 1
            else:
                l += 1

def main():
    n = getN()
    for _ in range(n):
        solve()

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

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

def divisor(x):
    ret = []
    for i in range(1, int(x**0.5)+1):
        if x % i == 0:
            ret.append(i)
            if i*i != x:
                ret.append(x//i)
    return ret

divisor_dict = {}
for i in range(len(A)):
    div = divisor(A[i])
    for j in div:
        if j in divisor_dict:
            divisor_dict[j] += 1
        else:
            divisor_dict[j] = 1

max_val = 0
for key, val in divisor_dict.items():
    if val >= N-1 and key > max_val:
        max_val = key

print(max_val)


### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split()))

def gcd(a, b):
    if a < b:
        b, a = a, b
    if b == 0:
        return a
        
    while a % b != 0:
        a %= b
        a, b = b, a

    return b

L = [0] * (N+1)
R = [0] * (N+2)

for i in range(1, N+1):
    ind = N+1-i
    L[i] = gcd(L[i-1], A[i-1])
    R[ind] = gcd(R[ind+1], A[ind])

ret = []
for i in range(1, N+1):
    ret.append(gcd(L[i], R[i+1]))

print(max(ret))
### BUGGY CODE ###

import sys
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
temp = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
        temp = temp+vertices[node]
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue.append([s,0])
done =set()
while(len(queue)>0 ):
    next=queue.pop(0)
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        bfs(temp, next[1] + 1)
        bfs(temp, next[1] + 2)
print(max(jumpValue[t][0]//3,-1))

### FIXED CODE ###

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
queue = []
def bfs(arr,jump):
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        if jumpValue[t][0]!=-1:
            break
print(max(jumpValue[t][0]//3,-1))
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())

def allequal(s):
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[0][0]:
                return False
    return True

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

def val(s):
    global n
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[j][i]:
                return False
    return True

if allequal(s):
    print(n**2)
else:
    res = 0
    for k in range(0,n):
        if val(plusb(s,k)):
            res += n
    print(res)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
st=list(map(''.join,zip(*s)))

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

res = 0
for i in range(n):
    if plusa(st,i) == plusb(s,i):
        res += n

print(res)
### BUGGY CODE ###

from operator import itemgetter
from collections import defaultdict
N = int(input())
A = [int(v) for v in input().split()]
cnt = 0
left_list = [i + a for i, a in enumerate(A, 1)]
right_list = [i - a for i, a in enumerate(A, 1)]
right_dict = defaultdict(set)
for i, right in enumerate(right_list, 1):
    right_dict[right].add(i)
for i, left in enumerate(left_list, 1):
    pair_num = len(right_dict[left] - set([i]))
    cnt += pair_num
print(cnt)

### FIXED CODE ###

from operator import itemgetter
from collections import defaultdict
N = int(input())
A = [int(v) for v in input().split()]
cnt = 0
left_list = [i + a for i, a in enumerate(A, 1)]
right_list = [i - a for i, a in enumerate(A, 1)]
right_dict = defaultdict(set)
for i, right in enumerate(right_list, 1):
    right_dict[right].add(i)
for i, left in enumerate(left_list, 1):
    pair_num = len(right_dict[left])
    cnt += pair_num
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W+1) for i in range(N+1)]

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

    print(dp[N][W])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0] * (W+1) for i in range(N+1)]

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

    print(dp[N][W])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()