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

l = raw_input().split()
N = int(l[0])
M = int(l[1])

BC = []

l = raw_input().split()
A = [int(x) for x in l]

for i in range(M):
    l = raw_input().split()
    bc = [int(l[0]), int(l[1])]
    BC.append(bc)

A.sort()
BC.sort(key = lambda x: x[1])
# print(N, M, A, BC)

for i in range(M):
    # print(BC[i])
    b = BC[i][0]
    c = BC[i][1]
    count = 0
    index = 0
    for j in range(N):
        if A[j] >= c:
            break
        if j < b:
            count += 1
        index += 1
    # print(count, index, A)
    A[index:index] = [c]*count
    del A[:count]
    # print(A)

# print(A)
print(sum(A))


### FIXED CODE ###

l = raw_input().split()
N = int(l[0])
M = int(l[1])

BC = []

l = raw_input().split()
A = [int(x) for x in l]

for i in range(M):
    l = raw_input().split()
    bc = [int(l[0]), int(l[1])]
    BC.append(bc)

A.sort()
BC.sort(key = lambda x: -x[1])
# print(N, M, A, BC)

i0 = 0
i1 = 0
for i in range(N):
    # print(BC[i0])
    b = BC[i0][0]
    c = BC[i0][1]

    if A[i] < c:
        A[i] = c
        i1 += 1
    if i1 == b:
        i0 += 1
        i1 = 0
    # print(A)
    if i0 == M:
        break

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

N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    C[p] += x

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        if b not in list:
            stack.append(b)
            C[b] += C[a]
C.pop(0)
print(*C)


### FIXED CODE ###

N,Q = map(int,input().split())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*(N)
for i in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
from collections import deque
d=deque()
d.append(0)
t = [False]*(N)
t[0] = True
while d:
    a = d.popleft()
    for b in G[a]:
        if not t[b]:
            t[b] = True
            d.append(b)
            C[b] += C[a]
print(*C)
### BUGGY CODE ###

import heapq as hq
N, K = map(int, input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort()
q = [(-A[i]*F[N-1-i], F[N-1-i]) for i in range(N)]
hq.heapify(q)
cnt = 0
while cnt < K:
	cnt += 1
	c = hq.heappop(q)
	if c[0] < 0:
		hq.heappush(q, (c[0]+c[1], c[1]))
	else:
		hq.heappush(q, c)
		break
print(-hq.heappop(q)[0])

### FIXED CODE ###

import heapq as hq
N, K = map(int, input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort()

if sum(A) <= K:
	print(0)
	exit()
ans = max([A[i]*F[N-1-i] for i in range(N)])

def achievable(score):
	cnt = 0
	for i in range(N):
		a,f = A[i], F[N-1-i]
		if a*f > score:
			n = score // f
			cnt += a-n
			if cnt > K:
				return False
	return True

l,r = 0, ans
while r - l > 1:
	p = (l + r) // 2
	if achievable(p):
		r = p
	else:
		l = p
print(r)
### BUGGY CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    # b = list(map(int, input().split()))
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)
    
  if check(b) != True:
    print(-1)
    
def check(B):
  # if 'get_ipython' in globals(): print(B)
  lenB = len(B)
  if lenB == 0 :
    return True
  for i in reversed(range(lenB)):
    if B[i] == i+1:
      if check(B[:i]+B[(i+1):]) == True:
        print(B[i])
        return True
        break
    
main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
### BUGGY CODE ###

N, K = map( int, input().split())
H = list( map( int, input().split()))
dp = [0]*N
for i in range(1,N):
    h = H[i]
    now = dp[i-1] + abs( h - H[i-1])
    for j in range( max(i-K,0), i):
        if now > dp[j] + abs( h - H[j]):
            now = dp[j] + abs( h - H[j])
    dp[i] = now
print( dp[-1])


### FIXED CODE ###

N, K = map( int, input().split())
H = list( map( int, input().split()))
dp = [0]*N
for i in range(1,N):
    h = H[i]
    now = dp[i-1] + abs( h - H[i-1])
    for j in range( max(i-K,0), i):
        if now > dp[j] + abs( h - H[j]):
            now = dp[j] + abs( h - H[j])
    dp[i] = now
print( dp[-1])
### BUGGY CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
  print(-1)
  exit()

a = 7
ans = 0
for i in range(10**7):
  if a % k == 0:
    ans = i + 1
    break
  else:
    a = a*10 + 7
    ans = i + 1


print(ans)


### FIXED CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
  print(-1)
  exit()

a = 7
ans = 0
for i in range(10**7):
  a = a % k
  if a % k == 0:
    ans = i + 1
    break
  else:
    a = a*10 + 7
    ans = i + 1


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

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

a.sort()
bc.sort(key=lambda x:x[1])
b=[]

for item in bc[::-1]:
  b=b+[item[1],]*item[0]
ans=0
len_b=len(b)
#print(a,b,bc)
for i in range(min(len_b,n)):
  if a[i]<b[i]:
    ans=ans+b[i]
  else:
    ans=ans+a[i]
if len_b<n:
  ans=ans+sum(a[len_b:])
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from operator import itemgetter
 
N,M = map(int,readline().split())
a = list(map(int,readline().split()))
m = map(int,read().split())
bc = list(zip(m,m))


#[n,m]=[int(x) for x in input().split()]
#a=[int(x) for x in input().split()]
#bc=[[int(x) for x in input().split()] for _ in range(m)]

bc.sort(key = itemgetter(1),reverse=True)
bc.append((N,-1))
change=[]
for b,c in bc:
    change += [c] * b
    if len(change) > N:
        break
 
a += change
a.sort()
answer = sum(a[-N:])
print(answer)
### BUGGY CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
for i in range(len(s)):
    ans[tmp%2019]+=1
    tmp=pow(10,i)*int(s[-i-1])+tmp
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)

### FIXED CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=1
rs=reversed(s)
for i in rs:
    ans[tmp%2019]+=1
    tmp=(tmp+int(i)*a)%2019
    a*=10
    a%=2019
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)
### BUGGY CODE ###

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

memo = [None] * (N + 1)
memo[0] = ''
# for Ai in A:
#     memo[tab[Ai]] = str(Ai)

ERROR_CODE = 'a'

import sys
sys.setrecursionlimit(10000)

def dp(X):
    global ERROR_CODE
    # print("#", X)
    if X < 0: return ERROR_CODE
    if memo[X] != None: return memo[X]
    len_max = 0
    rets = []
    for Ai in A:
        ret_tmp = str(Ai) + dp(X - tab[Ai])
        if ret_tmp[-1] == ERROR_CODE: continue
        ret_tmp = ''.join(sorted(list(ret_tmp), key=lambda x: -int(x)))
        rets.append(ret_tmp)
        len_max = max(len_max, len(ret_tmp))
    for i in range(len(rets)):
        rets[i] = '0' * (len_max - len(rets[i])) + rets[i]
    #
    rets.sort()
    # print("#", rets)
    if len(rets) == 0:
        ret = ERROR_CODE
    else:
        ret = rets[-1].replace('0', '')
    #
    memo[X] = ret
    return ret

ans = dp(N)
print(ans)
# print("#", memo)

### FIXED CODE ###

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if X < 0: return -(1000000007)
    if memo[X] != None: return memo[X]
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

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

s = input()
n = len(s)
mod = 10**9+7

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) % mod
        k *= 3**(hr+hl-2)
        ans += int(k) % mod
print(ans%mod)


### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7

moji = [[0,0,0,0] for _ in range(n+1)]

for i in range(1,n+1):
    for k in range(4):
        moji[i][k] += moji[i-1][k]
    if s[i-1] == 'A':
        moji[i][0] += 1
        continue
    elif s[i-1] == 'B':
        moji[i][1] += 1
        continue
    elif s[i-1] == 'C':
        moji[i][2] += 1
        continue
    else:
        moji[i][3] += 1

h = s.count('?')
mt = [1]
for i in range(h+1):
    mt.append(mt[-1]*3 % mod)
mt += [1/9,1/3]
ans = 0
for i in range(n):
    al,cr,hl,hr = moji[i][0], moji[n][2]-moji[i+1][2], moji[i][3], moji[n][3]-moji[i+1][3]
    if s[i] == 'B' or s[i] == '?':
        k = (al*3 + hl) * (cr*3 + hr) * mt[hr+hl-2]
        ans += int(k) % mod
print(ans%mod)
### BUGGY CODE ###

a = int(input())
b = a
while b % 2 != 0 or b % a != 0:
    b += 1
print(b)

### FIXED CODE ###

a = int(input())
if a % 2 == 0: 
    print(a)
else:
    print(2*a)
### BUGGY CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].append(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += dp[0][nxt]
            if len(tmp):
                dp[i][j] = list(set(tmp))
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


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

import itertools

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

ilist = list(range(K + 1))
ilist = ilist * 3
comb = set(i for i in list(itertools.combinations(ilist, 3)) if sum(i) == S)

print(len(comb))

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0

s3 = s // 3
m = max(k, s3)
for x in range(0, m + 1):
    # print(x)
    for y in range(0, m + 1):
        ad = s - x - y
        if ad <= k and ad >= 0:
            ans += 1

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

N = int(input())
p = list(map(float, input().split()))

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[1][0] = 1 - p[0]
dp[1][1] = p[0]
for i in range(2, N + 1):
    for j in range(N + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
        else:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
M = N // 2 + 1
ans = 0
for i in range(M, N + 1):
    ans += dp[-1][i]
print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[1][0] = 1 - p[0]
dp[1][1] = p[0]
for i in range(2, N + 1):
    for j in range(N + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
        else:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
M = N // 2 + 1
ans = 0
for i in range(M, N + 1):
    ans += dp[-1][i]
print(ans)
### BUGGY CODE ###

from math import factorial
n, a, b = map(int, input().split())
a1 = factorial(n) / factorial(a) / factorial(n - a)
b1 = factorial(n) / factorial(b) / factorial(n - b)
ans = 2**n - a1 - b1 - 1 
print(int(ans)%1000000007)

### FIXED CODE ###

def nCr(n,r):
    num = den = 1

    for i in range(r):
        num = (num*(n-i)) % MOD #n*(n-1)*...*(n-r)
        den = (den*(i+1)) % MOD #1*2*...*r
    
    return (num * pow(den, MOD-2, MOD)) % MOD
    #フェルマーの小定理を使うことで1/denを作っている
    #最終的に(n*...*(n-r))/(1*...*r)

MOD = 10**9 + 7
n, a, b = map(int, input().split())
x = pow(2, n, MOD)

print((x - nCr(n,a) - nCr(n,b) -1 )% MOD)
### BUGGY CODE ###

N, M =map(int, input().split())
li = []
l, r = map(int, input().split())
for j in range(r-l+1):
    li.append(j + l)
for i in range(M-1):
    l, r = map(int, input().split())
    # for j in range(r-l+1):
    li = [s for s in li if l <= s and s <= r]
print(len(li))

### FIXED CODE ###

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

l, r = map(int, input().split())

for i in range(M-1):
    l2, r2 = map(int, input().split())
    if l2 > l:
        l = l2
    if r > r2:
        r = r2
if r - l + 1 > 0:
    print(r - l + 1)
else:
    print(0)
### BUGGY CODE ###

from itertools import permutations
n,m,r=map(int,input().split())
d = [[10**12]*n for j in range(n)]
l=[int(i)-1 for i in input().split()]
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      if d[i][j]>d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
#print(d)
ans=10**12
for v in permutations(l):
  cnt=sum(d[v][u] for v, u in zip(v, v[1:]))
  ans=min(ans,cnt)
print(ans)


### FIXED CODE ###

import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
A = max(a)
b = sorted(a)[-2]
if a.count(A) > 1:
    for i in range(len(a)):
        print(A)
else:
    for i in range(len(a)):
        if i == a.index(A):
            print(b)
        else:
            print(A)

### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
A = max(a)
b = sorted(a)[-2]
if a.count(A) > 1:
    for i in range(len(a)):
        print(A)
else:
    for i in range(len(a)):
        if a[i] == A:
            print(b)
        else:
            print(A)
### BUGGY CODE ###

#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(list)
for i in range(len(s)):
    cum[i+1]=cum[i]+int(s[i])
for i in range(len(s)+1):
    d[cum[i]%3].append(i)
ret = 0
#print(cum,d)
for l in d.values():
    #print(l)
    n = len(l)
    can = [[l[i],l[j]] for i in range(n) for j in range(i,n) if l[j] > l[i]+3]
    #print(can)
    #print([[i,j,int(s[i:j])] for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    #print([1 for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0])
    ret += sum(1 for i,j in can if int(s[i:j])>2019 and int(s[i:j])%2019==0)
print(ret)

### FIXED CODE ###

# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
arr = np.array([int(i) for i in input().split()])

max = t = sum(arr[0:k])
max_p = sum([_*(_+1)/(_*2.0) for _ in arr[0:k]])

for i in range(1, n-k+1):
  t += arr[i+k-1]
  t -= arr[i-1]
  if max < t:
    max = t
    max_p = sum([_*(_+1)/(_*2.0) for _ in arr[i:i+k]])

print(max_p)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
arr = np.array([int(_)*(int(_)+1)/(int(_)*2.0) for _ in input().split()])

max = t = sum(arr[0:k])

for i in range(1, n-k+1):
  t += arr[i+k-1]
  t -= arr[i-1]
  if max < t:
    max = t

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

n=int(input())
a=list(map(int,input().split()))
x=1
for i in range(n):
    x=x*a[i]

if x>10**18:
    print(-1)
        
   

        
else:
    print(x)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=1
c=0
if a.count(0)>0:
    print(0)
else:
    for i in range(n):
        x=x*a[i]

        if x>10**18:
            print(-1)
            c=1
            break        

        
    if c==0:
        print(x)
### BUGGY CODE ###

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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (n, ) = [int(e) for e in lines[0].split(' ')]

    return (n, )


def solve(n, ):

    
    a = []
    tmp = n
    total = 0
    while tmp > 0:
        q = tmp // 10
        r = tmp % 10
        #a.append(r)
        total = total + r
            
        tmp = q

    a.reverse()
    if debug:
        log("a=%s" % a)

    result = 'No' 
    #if sum(a) % 9 == 0:
    if total % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

### FIXED CODE ###

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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = lines[0]

    return (n, )


def solve(n, ):

    
    total = sum([int(e) for e in n])

    result = 'No' 
    #if sum(a) % 9 == 0:
    if total % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
### BUGGY CODE ###

N,W=map(int,input().split())
S = [[0 for j in range(2)] for i in range(N+1)]

DP= [[0]*100010  for i in range(110)]
def chmax(a,b):
    if a>b:
        return a
    else:
        return b


for i in range(N):
    w,v=map(int,input().split())
    S[i][0]=w
    S[i][1]=v


for i in range(N):
    for j in range(W+1):
        if j-S[i][0]>=0:
            
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-S[i][0]]+S[i][1])
        
        else:
            DP[i+1][j]=DP[i][j]
        
print(DP[N][W])


### FIXED CODE ###


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


#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S

weight=[0]*110
value=[0]*110

S = [[0 for j in range(3)] for i in range(100010)]
DP= [[0 for j in range(100100)] for i in range(110)]

for i in range(N):
    A,B=map(int,input().split())
    weight[i]=A
    value[i]=B
    
for i in range(N):
    for w in range(W+1):
        if w>=weight[i]:
            DP[i+1][w]=max(DP[i][w-weight[i]]+value[i],DP[i][w])
        else:
            DP[i+1][w]=DP[i][w]

print(DP[N][W])
### BUGGY CODE ###

#numpyで数えていたのを変更
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
c=Counter(A)
c_all_ones=Counter()
for key in c.keys():
    c_all_ones[key]=1
Dx=[0]
for i in range(1,N+1):
    Dx.append(len(c))
    c.subtract(c_all_ones)
    c=+c #0以下を削除

Sx=[0]#初項は0
for j in range(1,N+1):
    Sx.append(Sx[j-1]+Dx[j])

#Sxが作れたので、xに関して二分探索をする
for k in range(1,N+1):
    x_min=0
    x_max=N+1
    while x_max>x_min+1:
        x_mid=(x_max+x_min)//2
        if Sx[x_mid]>=k*x_mid:
            x_min=x_mid
        else:
            x_max=x_mid
    print(x_min)

### FIXED CODE ###

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

c = [0] * (N + 1)
Dx = [0] * (N + 1)
for a in A:
    c[a] += 1 #cは、aという数が出た回数を記録
    Dx[c[a]]+=1
    #Dxは、その回数のところに種類を記録。賢い。

Sx=[0]#初項は0
for j in range(1,N+1):
    Sx.append(Sx[j-1]+Dx[j])
#解法2を真似してみる。
for h in range(1,N+1):
    Sx[h]=Sx[h]/h

x=N
k=1
while k<N+1:
    if x<0:
        for _ in range(N-k+1):
            print(0)
        exit(0)
    if k<=Sx[x]:
        print(x)
        k+=1
    else:
        x-=1
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s_uniq = list(set(s))
result = 0
 
for s_uniq_i in s_uniq:
    count = s.count(s_uniq_i)
    if count >= 2:
        result += count * (count-1) // 2
 
print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

print(result)