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

from collections import deque
N, M = map(int, input().split())

A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = deque()

while len(C) < M:
    for j in range(B[A.index(min(A))]):
        if len(C) < M:
            C.append(min(A))
        else:
            break
    B.pop(A.index(min(A)))
    A.remove(min(A))

C = sorted(C)
print(sum(C[:M]))

### FIXED CODE ###

import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline
N, M = map(int, input().split())

A = deque()
for i in range(N):
    A.append(list(map(int, input().split())))

A = sorted(A, key=itemgetter(0))

m=0
cost=0

for i in range(N):
    if m >= M:
        break
    buy = min(M - m, A[i][1])
    cost += A[i][0] * buy
    m += buy

print(cost)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import bisect

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

    L = sorted(L)

    ans = 0
    for i in range(N-2):
        for j in range(N-1):
            if j > i:
                ans += bisect.bisect_left(L[j+1:], L[i] + L[j]) - bisect.bisect_left(L[j+1:], L[j] - L[i])

    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import bisect

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

    L = sorted(L)

    ans = 0
    for i in range(N-2):
        for j in range(N-1):
            if j > i:
                ans += bisect.bisect_left(L[j+1:], L[i] + L[j])

    print(ans)

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

import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    l = [i for i in range(1,k+1)]
    p_list = list(itertools.combinations_with_replacement(l,3))
    for i in p_list:
        ans += gcd(gcd(i[0],i[1]),i[2])*(6//math.factorial((4-len(set(i)))))
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

### FIXED CODE ###

from math import gcd
def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

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

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

from itertools import permutations

lis = [i for i in range(N)]

scores = []
for i, v in enumerate(permutations(lis, N)):
    score = 0
    for j in range(N): 
        score += abs(v.index(j)-j) * A[j]
    scores.append(score)

print(max(scores))

### FIXED CODE ###

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)
### BUGGY CODE ###

import numpy as np
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
dp[0][0] = 0
dp = np.array(dp)
value = np.array(value)
weight = np.array(weight)
for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[-1][i] <= W:
        ans = i
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
dp[0][0] = 0

for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[-1][i] <= W:
        ans = i
print(ans)
### BUGGY CODE ###

import fractions
MOD = 1000000000+7

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

def lcm(a,b):
  return a*b//fractions.gcd(a,b)

a_lcm = A[0]
for a in A[1:]:
  a_lcm = lcm(a_lcm, a)

ans = 0
for a in A:
  ans += a_lcm//a
print(ans%MOD)


### FIXED CODE ###

import fractions
MOD = 1000000000+7

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

def lcm(a,b):
  return a*b//fractions.gcd(a,b)

a_lcm = A[0]
for a in A[1:]:
  a_lcm = lcm(a_lcm, a)

ans = 0
for a in A:
  ans += a_lcm//a
print(ans%MOD)
### BUGGY CODE ###

import numpy as np
n,x,y = map(int, input().split())
t = np.zeros(n)
x = x-1
y = y-1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    b = abs(i-j)
    if a < b:
      t[a-1] += 1
    else:
      t[b-1] += 1

for k in range(0,n-1):
  print(int(t[k]))

### FIXED CODE ###

n,x,y = map(int, input().split())
t = [0 for i in range(n)]
x = x-1
y = y-1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    b = abs(i-j)
    if a < b:
      t[a-1] += 1
    else:
      t[b-1] += 1

for k in range(0,n-1):
  print(int(t[k]))
### BUGGY CODE ###

import copy
N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        if i <= x:
            if abs(i +j -x) <= abs(y - i -j):
                A[i][i+j] = j
            elif abs(i + j -x) > abs(y - i -j):
                A[i][i + j] = x-i + 1 + abs(y - (i+j))
        elif i>x:
            if abs(x-i)<= abs(y-i):
                A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
            else:
                A[i][i+j] = j
A[X-1][Y-1] = 1
for t in range(N):
    if t == 0:
        continue
    sum = 0
    for u in range(N):
        sum = sum + A[u].count(t)

    print(sum)




### FIXED CODE ###


N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1
ans = [0] * (N)
A = [[] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        path = min(abs(x- i) +1 +abs(y-i-j),j)
        ans[path] += 1
for _ in range(len(ans)):
    if _ == 0:
        continue
    print(ans[_])
### BUGGY CODE ###

n=int(input())
s=list(input())
c=0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if s[i-1]==s[j-1]:
            continue
        for k in range(j+1,n+1):
            if s[k-1]!=s[j-1] and s[i-1]!=s[k-1]:
                if j-i != k-j:
                    c+=1
print(c)

### FIXED CODE ###

N = int(input())
S = input()
 
r = S.count('R')
g = S.count('G')
b = S.count('B')
max = r * g * b 
 
count = 0
for i in range(N-2):
	for j in range(i+1, N-1):
		k = 2 * j - i
		if k > N - 1:
			break
	
		if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
			count += 1
		
		
 
print(max - count)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))

#%%
d = defaultdict(lambda: 0)
for key in A:
    d[key] += 1

for a in A:
    ans = 0
    for k, v in d.items():
        if k == a:
            v -= 1
        ans += v * (v - 1)//2
    print(ans)




### FIXED CODE ###

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))

#%%
d = defaultdict(lambda: 0)
for key in A:
    d[key] += 1

#%%
# それぞれのkeyのnC2
cmb = dict()
cmb2 = dict()
for k in d.keys():
    cmb[k] = d[k] * (d[k] - 1) // 2
    cmb2[k] = (d[k] - 1) * (d[k] - 2) // 2

#%%
ans_d = dict()
s = sum(cmb.values())
for k in d.keys():
    ans_d[k] = s - cmb[k] + cmb2[k]
#%%
for a in A:
    print(ans_d[a])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
N,Q=map(int, input().split())
tree_dist={}
for i in range(N):
    tree_dist[i+1] = set()
for i in range(N-1):
    a,b = map(int, input().split())
    tree_dist[a].add(b)
    tree_dist[b].add(a)
    
z=[0]*N
for i in range(Q):
    p,x = map(int, input().split())
    z[p-1] += x

def saiki(i,p):
    L = list(tree_dist[i])
    for l in L:
        if l == p:
            continue
        z[l-1] += z[i-1]
        saiki(l,i)
saiki(1,0)
print(" ".join(map(str,z)))




### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
input=lambda :sys.stdin.readline()
N,Q=map(int, input().split())
tree_dist={}
for i in range(N):
    tree_dist[i+1] = []
for i in range(N-1):
    a,b = map(int, input().split())
    tree_dist[a].append(b)
    tree_dist[b].append(a)
    
z=[0]*N
for i in range(Q):
    p,x = map(int, input().split())
    z[p-1] += x

def saiki(i,p):
    L = list(tree_dist[i])
    for l in L:
        if l != p:
            z[l-1] += z[i-1]
            saiki(l,i)
saiki(1,0)
print(" ".join(map(str,z)))
### BUGGY CODE ###

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

res = 0
d = {}

d_res = {}

for i in range(N):
    if l[i] in d:
        d[l[i]] += 1
    else:
        d[l[i]] = 1



def get_n(d, x):
    res = 0
    for k,v in d.items():
        if k == x:
            res += ((v-1) * (v-2))/2
        else:
            res += (v * max(0,v-1))/2
    res = int(res)
    d_res[x] = res
    return res


for e in l:
    if e in d_res:
        print(d_res[e])
    else:
        print(get_n(d, e))


### FIXED CODE ###

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

d = {}


for i in range(N):
    if l[i] in d:
        d[l[i]] += 1
    else:
        d[l[i]] = 1

max_comb = 0
for v in d.values():
    max_comb += v * max(0, (v-1)) /2

def get_n(x):

    return int(max_comb - d[x] +1)


for e in l:
    print(get_n(e))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for a in range(N):
    for b in range(a + 1, N):
        for c in range(b + 1, N):
            if L[c] >= L[a] + L[b]:
                break
            elif L[a] >= L[b] + L[c] or L[b] >= L[c] + L[a]:
                continue
            else:
                count += 1
print(count)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for a in range(N):
    for b in range(a + 1, N):
        c = bisect.bisect_left(L, L[a] + L[b])
        if c > b:
            count += c - b - 1
        else:
            break
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    A = [int(input()) for _ in range(M)]
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print(ans[N] % MOD)
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    A = set([int(input()) for _ in range(M)])
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print(ans[N] % MOD)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
con = 1;
a = 1;
b = 1;
 
for i1 in range(n):
    con = (con * 10);
for i2 in range(n):
    a = (a * 9);
for i3 in range(n):
    b = (b * 8);
 
c = 2*a - b;
con = (con - c)%1000000007;
print(con)

### FIXED CODE ###

n = int(input())
con = 1;
a = 1;
b = 1;

for i1 in range(n):
    con = (con * 10) % 1000000007;
for i2 in range(n):
    a = (a * 9) % 1000000007;
for i3 in range(n):
    b = (b * 8) % 1000000007;

c = (2*a - b)%1000000007;
con = (con - c)%1000000007;
print(con)
### BUGGY CODE ###

from decimal import *
N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
hope = []
for i in range(N):
  hope.append(Decimal((P[i]+1)/2))

for j in range(N-K+1):
  ans = max(ans,sum(hope[j:j+K]))

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

# 約数の全列挙
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort(reverse=True)  # ソート
    return divisors

def sol():
    A, B = map(int, input().split())

    divA = divisors(A)
    comDiv = []

    for a in divA:
        if B % a == 0:
            comDiv.append(a)

    comDiv.sort()
    isIndep = [True] * len(comDiv)
    maxDiv = comDiv[-1]
    divToIndex = {d : i for i, d in enumerate(comDiv)}
    ans = 1

    for i, div in enumerate(comDiv[1:], start=1):
        if isIndep[i]:
            ans += 1
            mul = 2
            while div * mul <= maxDiv:
                if div * mul in divToIndex:
                    isIndep[divToIndex[div * mul]] = False
                mul += 1

    print(ans)

sol()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

def sol():
    A, B = map(int, input().split())

    primeA = primeCount(A)
    primeB = primeCount(B)

    ans = 1
    for a in primeA.keys():
        if a in primeB:
            ans += 1

    print(ans)

sol()
### BUGGY CODE ###

n = int(input())
s = [int(i) for i in input().split()]
S = sorted(set(s), key=s.index)
q = int(input())
t = [int(i) for i in input().split()]
T = sorted(set(t))

copy = S[:]
count = 0
for v in T:
    S = copy[:]
    while True:
        if len(S) == 0: break
        if v == S[len(S)//2]:
            count += 1
            break
        elif v > S[len(S)//2]:
            S[:] = S[len(S)//2+1:]
        elif v < S[len(S)//2]:
            S[:] = S[:len(S)//2]

print(count)

### FIXED CODE ###

n = int(input())
S = set(int(i) for i in input().split())
q = int(input())
T = set(int(i) for i in input().split())
print(len(S & T))
### BUGGY CODE ###

import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了：sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    S = input()

    while 1:
        if S == '':
            print('YES')
            sys.exit()
        elif re.search('dreamer$', S):
            S = S[:-7]
            # print('a', S)
        elif re.search('eraser$', S):
            S = S[:-6]
            # print('b', S)
        elif re.search('dream$', S):
            S = S[:-5]
            # print('c', S)
        elif re.search('erase$', S):
            S = S[:-5]
            # print('d', S)
        else:
            print('NO')
            sys.exit()

    print('YES')

if __name__ == "__main__":
    main()

### FIXED CODE ###

import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了：sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    S = input()

    while 1:
        if S == '':
            print('YES')
            sys.exit()
        elif end_match('dreamer', S):
            S = S[:-7]
            # print('a', S)
        elif end_match('eraser', S):
            S = S[:-6]
            # print('b', S)
        elif end_match('dream', S):
            S = S[:-5]
            # print('c', S)
        elif end_match('erase', S):
            S = S[:-5]
            # print('d', S)
        else:
            print('NO')
            sys.exit()

def end_match(query, S):
    length = len(query)
    end = S[-length:]
    # print(query, end)
    if end == query:
        return True
    else:
        return False

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

n = int(input())
s = []
for i in range(n):
	s.append("".join(sorted(input())))
	

ans = 0
for i in range(n-1):
	for j in range(i+1, n):
		if s[i] == s[j]:
			ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
st = {}
sv = {}
for i in range(n):
	tmp = "".join(sorted(input()))
	if tmp in st.keys():
		sv[tmp] += st[tmp]
		st[tmp] += 1
	else:
		st[tmp] = 1
		sv[tmp] = 0


print(sum(sv.values()))
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
mae = 1
for i in range(K):
    mae *= A[i]
for i in range(N-K):
    ato = mae/A[i]*A[i+K]
    #mae = ato
    if ato > mae:
        print("Yes")
    else:
        print("No")
    mae = ato


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N-K):
    if A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from operator  import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

"""
kari1 = '100000 100000 99990 99990'
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0]) #縦Hマス
W = int(in1[1]) #横Wマス
A = int(in1[2]) #下からAマス
B = int(in1[3]) #左からBマス

allCNT = 0
for idx1 in range(W - B):
    beforeCNT = combinations_count((H - A - 1) + B + idx1, (H - A - 1))
    afterCNT  = combinations_count((A - 1) + (W - B - 1 - idx1), (A - 1))
    allCNT    = allCNT + (beforeCNT * afterCNT)

allCNT = allCNT % ((10 ** 9) + 7)

print(allCNT)


### FIXED CODE ###

from operator  import mul
from functools import reduce

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6
fact    = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv     = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#kari1 = '2 3 1 1'                   #2
#kari1 = '10 7 3 4'                  #3570
#kari1 = '100000 100000 99999 99999' #1
#kari1 = '100000 100000 44444 55555' #738162020

"""
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0])
W = int(in1[1])
A = int(in1[2])
B = int(in1[3])

allCNT = 0
for idx1 in range(W - B):
    beforeCNT = cmb(H - A + B - 1 + idx1, H - A - 1, p)
    afterCNT  = cmb(W + A - B - 2 - idx1, A - 1, p)
    allCNT    = (allCNT + (beforeCNT * afterCNT) % p) % p

print(allCNT)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    for i in range(1, N+1):
        for j in range(N-i+1):
            if sum(A[j:j+i]) == 0:
                count += 1
    return count

if __name__ == '__main__':
    print(main())



### FIXED CODE ###

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

    s = [0 for _ in range(N+1)]
    for i in range(N):
        s[i+1] = s[i] + A[i]
    s.sort()
    n = 1
    for i in range(N):
        if s[i+1] == s[i]:
            n+=1
        else:
            count += n*(n-1)//2
            n = 1
    count += n*(n-1)//2
    return count

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

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.remove(m)
    else:
        arr += [m]
print(len(arr))

### FIXED CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = set()
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.remove(m)
    else:
        arr.add(m)
print(len(arr))
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main(init=int(2**31-1)):
    n, q = (int(s) for s in stdin.readline().split())

    a = [init] * n
    b = {}

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            try:
                m = b[(x, y)]
            except KeyError:
                m = min(a[x:y+1])
                b[(x, y)] = m
            print(m)
        else:
            a[x] = y
            for i, j in b.keys():
                if i <= x <= j:
                    del b[(i, j)]


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main(init=int(2**31-1), readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    a = [init] * n
    b = [init] * ((n // 100) + 1)

    for _ in range(q):
        com, x, y = (int(s) for s in readline().split())
        if com:
            bx = x - (x % 100) + 100
            by = y - (y % 100)
            if bx < by:
                m = min(min(a[x:bx]), min(b[bx//100:by//100]),
                        min(a[by:y+1]))
            else:
                m = min(a[x:y+1])
            print(m)
        else:
            a[x] = y
            bx = x - (x % 100)
            b[x//100] = min(a[bx:bx+100])


main()