Harryxun/stf_run huggingface dataset:
import math

def main():
    num, goal = map(int, input().split())
    data = [0] + [list(map(int, input().split())) for i in range(num)]

    ans_num = 1000

    for i in range(num ** 2):
        bin_str = bin(i)
        bin_list = list(bin_str[2:])
        bin_list = ['0' for i in range(num - len(bin_list))] + bin_list
        bin_list.reverse()

        sum_value = 0
        now_num = 0

        for j in range(len(bin_list)):
            if bin_list[j] == '1':
                sum_value += data[j+1][0] * (j + 1) * 100 + data[j+1][1]
                now_num += data[j+1][0]

        if sum_value < goal:
            for j in range(len(bin_list))[::-1]:
                if bin_list[j] == '1':
                    continue
                honsuu = math.ceil((goal - sum_value) / ((j + 1) * 100))
                sum_value += min(honsuu, data[j+1][0] - 1) * (j + 1) * 100
                now_num += min(honsuu, data[j+1][0] - 1)
                break

        if sum_value >= goal:
            if now_num < ans_num:
                ans_num = now_num

    print(ans_num)





if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():

    num, goal = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    ans = 10 ** 10

    for i in range(2 ** num):
        toku_flg = list(map(int, list(bin(i)[2:])))
        toku_flg = [0 for i in range(num - len(toku_flg))] + toku_flg

        now_score = 0
        now_mondai = 0
        for i in range(num):
            if toku_flg[i] == 1:
                now_score += (i + 1) * 100 * data[i][0] + data[i][1]
                now_mondai += data[i][0]

        if now_score < goal:
            for i in range(num)[::-1]:
                if toku_flg[i] == 0:
                    if now_score + (i + 1) * 100 * (data[i][0] - 1) < goal:
                        break
                    nokori = goal - now_score
                    add_num = math.ceil(nokori / ((i + 1) * 100))
                    now_score += (i + 1) * 100 * add_num
                    now_mondai += add_num
                    break

        if now_score >= goal:
            if now_mondai < ans:
                ans = now_mondai

    print(ans)





if __name__ == '__main__':
    main()
from collections import defaultdict
d = defaultdict(int)
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

S = input()
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

if len(S) < 26:
    for x in S:
        d[x] += 1
    for x in a:
        if d[x] == 0:
            print(S+x)
            exit()
else:
    index = 25
    for i in range(25):
        if S[i] > S[i+1]:
            index = i
            break
    ss = sorted(S[index-1:])
    print(S[:index-1] + ss[ss.index(S[i-1])+1])


### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

S = input()
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

if len(S) < 26:
    for x in S:
        d[x] += 1
    for x in a:
        if d[x] == 0:
            print(S+x)
            exit()
else:
    i = 25
    while S[i-1] > S[i]:
        i -= 1
    ss = sorted(list(S[i-1:]))
    t = S[i-1]
    print(S[:i-1] + ss[ss.index(t)+1])
while 1:
     s==input()
     if '?' in s: break
     print(int(eval(s)))


### FIXED CODE ###



while 1:
     s=input()
     if '?' in s: break
     print(int(eval(s)))
n, m, x = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
aa = a
for i in range(1, x):
    if a[0] == i:
        ans1 += 1
        a.pop(0)
if len(a) != 0:
    for i in range(x, n):
        if a[0] == i:
            ans2 += 1
            a.pop(0)
    

ans = min(ans1,ans2)
print(ans)

### FIXED CODE ###

n, m, x = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
if x == 1 or x == n:
    print(0)
else:
    for i in range(1, x):
        if len(a) != 0:
            if a[0] == i:
                ans1 += 1
                a.pop(0)
    if len(a) != 0:
        for i in range(x, n):
            if len(a) != 0:
                if a[0] == i:
                    ans2 += 1
                    a.pop(0)
    ans = min(ans1, ans2)
    print(ans)
n,k = map(int,input().split())
a = []
b = []
for i in range(n):
    tmp1,tmp2 = map(int,input().split())
    a.append(tmp1)
    b.append(tmp2)
counter = k-1
for i in range(n):
    counter = counter - b[i]
    if counter <= 0:
        print(a[i])
        break

### FIXED CODE ###

a,b,c = map(int,input().split())
if c >= a and c <=b:
    print("Yes")
else:
    print("No")
import numpy.math
while True:
    line = input().split(" ")
    if(len(line) != 2):
        exit()
    a = int(line[0])
    b = int(line[1])
    print(int(math.log10(a+b))+1)

### FIXED CODE ###

import math
while True:
    try:
        line = input().split(" ")
        print(int(math.log10(int(line[0])+int(line[1])))+1)
    except:
        break
while True:
    n = int( input() )
    if n==0:
        break
    a=list(map(int, input().split()))
    m=sum(a)/n
    s=0
    for i in a:
        s+=(i-m)**2
    print( ( s/n)**0.5 )

### FIXED CODE ###

n = int( input() )
x = list(map(int, input().split()))
y = list(map(int, input().split()))
for i in range(1,4):
    s=0
    m=0
    for j in range(n):
        s+=(abs(x[j]-y[j]))**i
        if (abs(x[j]-y[j])) > m:
            m=(abs(x[j]-y[j]))
    print(s**(1/i))
print(m)
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline
n = int(rl())
li = []
for _ in range(n):
  lis = list(map(int, rl().split()))
  li.append(lis)
t = 0
for i in list(collections.permutations(n)):
  for k in range(n-1):
    s = (li[i[k]][0] - li[i[k+1]][0])**2 + (li[i[k]][1] - li[i[k+1]][1])**2
    t += s**0.5
print(t/math.factorial(n))
  
  
  


### FIXED CODE ###

import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline
n = int(rl())
li = []
for _ in range(n):
  lis = list(map(int, rl().split()))
  li.append(lis)
t = 0
for i in list(itertools.permutations(range(n))):
  for k in range(n-1):
    s = (li[i[k]][0] - li[i[k+1]][0])**2 + (li[i[k]][1] - li[i[k+1]][1])**2
    t += s**0.5
print(t/math.factorial(n))
print(sum(s[0]==s[4]for s in map(str,range(*map(sum,enumerate(map(int,input().split()))))))if s[1]==s[3])

### FIXED CODE ###

print(sum(s[0]==s[4]and s[1]==s[3]for s in map(str,range(*map(sum,enumerate(map(int,input().split())))))))
n = int(input())
a = list(map(int, input().split()))
l = []
for i in a:
    count = 0
    for j in range(1, 31):
        if i%(2**j) == 0:
            count += 1
        else:
            l.append(count)
            break
print(min(l))

### FIXED CODE ###

s = input()
print(s.count("1"))
import math

def least_common_multiple(x,y):
    return (x * y) / math.gcd(x, y)
    
a,b = map(int,input().split(" "))

print(int(least_common_multiple(a,b)))

### FIXED CODE ###

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

import fractions
def lcm(x, y):
    return (x * y) / fractions.gcd(x,y)
    
print(int(lcm(a, b)))
n = int(input())
a = map(int, input().split())
while True:
  for i in range(n):
    if a[i] % 2 == 1:
      break
    a[i] = a[i] // 2
  else:
    ans += 1
    continue
  break
print(ans)

### FIXED CODE ###

n = int(input())
print(min(bin(int(i))[::-1].find("1") for i in input().split()))
# -*- coding: utf-8 -*-


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

s=0.5*(a+b)

int v= int(s)+1

print(v)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Nov  3 09:19:07 2018

@author: sk
"""

     
      
b, c = map(int, input().split())
     
s=0.5*(b+c)
     
d = int(s)
    
if s-d > 0:
    v=int(d+1)
else :
    v=int(d)
print(v)
A, B, C, K = list(map(int, input().split()))
if K % 2 == 0:
	print(A - B)
else:
	print(A - B) * (-1)

### FIXED CODE ###

A, B, C, K = list(map(int, input().split()))
if K % 2 == 0:
	print(A - B)
else:
	print((A - B)  * (-1))
A = list(map(int, input().split()))
L = len(A)
ans = [0, 0, 0, 0]
dx = A[2] - A[0]
dy = A[3] - A[1]
if(dx>0 and dy>=0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] - dy
    y3 = A[3] + dx
    x4 = x3 - dx
    y4 = y3 - dy
elif(dx>=0 and dy<0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] + dy
    y3 = A[3] + dx
    x4 = x3 - dx
    y4 = y3 + dy
elif(dx<=0 and dy<0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] + dy
    y3 = A[3] - dx
    x4 = x3 + dx
    y4 = y3 + dy
elif(dx<0 and dy>=0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] - dy
    y3 = A[3] - dx
    x4 = x3 + dx
    y4 = y3 - dy

ans[0] = str(x3)
ans[1] = str(y3)
ans[2] = str(x4)
ans[3] = str(y4)
ans = ' '.join(ans)
print(ans)

### FIXED CODE ###

A = list(map(int, input().split()))
L = len(A)
ans = [0, 0, 0, 0]
dx = A[2] - A[0]
dy = A[3] - A[1]
if(dx>=0 and dy>=0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] - dy
    y3 = A[3] + dx
    x4 = x3 - dx
    y4 = y3 - dy
elif(dx>0 and dy<0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] + dy
    y3 = A[3] + dx
    x4 = x3 - dx
    y4 = y3 + dy
elif(dx<=0 and dy<=0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] + dy
    y3 = A[3] - dx
    x4 = x3 + dx
    y4 = y3 + dy
elif(dx<0 and dy>0):
    dx = abs(dx)
    dy = abs(dy)
    x3 = A[2] - dy
    y3 = A[3] - dx
    x4 = x3 + dx
    y4 = y3 - dy

ans[0] = str(x3)
ans[1] = str(y3)
ans[2] = str(x4)
ans[3] = str(y4)
ans = ' '.join(ans)
print(ans)
import numpy as np
n=int(input())
count=[1]*(n+1)
x=[]#素因数格納
for i in range(2,n+1):
  if n%i==0 and count[i]==1:
    x.append(i)
    for j in range(2*i,n+1,i):
      count[j]=0
y=[]#指数
for i in x:
  c=1
  while n%(i**(c+1))==0:
    c+=1
  y.append(c)

def judge(y):
  i=1
  while np.arange(i+2).sum()<=y:
    i+=1
  return i
ans=0
for i in range(len(y)):
  ans+=judge(y[i])
print(ans)


### FIXED CODE ###

import numpy as np
n=int(input())
if n==1:
  print(0)
else:
  def factorization(n):
      arr = []
      temp = n
      for i in range(2, int(-(-n**0.5//1))+1):
          if temp%i==0:
              cnt=0
              while temp%i==0:
                  cnt+=1
                  temp //= i
              arr.append([i, cnt])

      if temp!=1:
          arr.append([temp, 1])

      if arr==[]:
          arr.append([n, 1])

      return arr

  y=factorization(n)
  def judge(y):
    i=1
    while np.arange(i+2).sum()<=y:
      i+=1
    return i
  ans=0
  for i in range(len(y)):
    ans+=judge(y[i][1])
  print(ans)
S = list(input())

out = "Good"

for i in range(0,4):
  if S[i] == S[i+1]:
    out = "Bad"
    
print(out)


  


### FIXED CODE ###

S = list(input())

out = "Good"

for i in range(0,3):
  if S[i] == S[i+1]:
    out = "Bad"
    
print(out)
H,A=map(int, input().split())
print(math.ceil(H/A))

### FIXED CODE ###

import math
H,A=map(int, input().split())
print(math.ceil(H/A))
import math

n = int(input())
s = int(input())

ans = -1

def f(b, n):
  if n < b:
    return n
  else:
    return f(b, n//b) + n % b

if n == s:
  ans = n+1

elif s == 1:
  ans = n
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn):
    if s == f(b, n):
      ans = b
      break
  else:
    for p in range(1, rootn):
      b = (n-s)//p + 1
      if s == p*b + n%b:
        ans = b
        break

print(ans)

### FIXED CODE ###

import math

n = int(input())
s = int(input())

ans = []

def f(b, n):
  if n < b:
    return n
  else:
    return f(b, n//b) + n % b

if n == s:
  ans.append(n+1) 
  
elif n < s:
  ans.append(-1)
  
else:
  rootn = int(math.sqrt(n))
  for b in range(2, rootn+2):
    if s == f(b, n):
      ans.append(b)
      break
      
  for p in range(1, rootn):
    b = (n-s)//p + 1
    if s == p + n%b:
      ans.append(b)
      
if not ans:
  ans.append(-1)

print(min(ans))
n,m = map(int,input().split())
hyo = list(map(int,input().split()))
all_hyo = sum(hyo)

hyo.sort(reverse=True)

a = True

for x in range(m):
  if hyo[m] < all_hyo / 4 / m:
    a = False
    break

if a :
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m = map(int,input().split())
hyo = list(map(int,input().split()))
all_hyo = sum(hyo)

hyo.sort(reverse=True)

a = True

for x in range(m):
  if hyo[x] < all_hyo / 4 / m:
    a = False
    break

if a :
  print("Yes")
else:
  print("No")
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
pn=[2]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        if (L+1)/2 in pn:
            pn.append(L)
pn.pop(0)
for i in range(q):
    print(len([i for i in pn if lr[i][0]<=i<=lr[i][1]]))

### FIXED CODE ###

q = int(input())
k = 10**5+1
x = [0]*k
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, n+1):
        if prime[i]:
            for j in range(i*2, n+1, i):
                prime[j] = False
    return prime

p = sieve(k+1)
c = 0
for i in range(3, k):
    if p[i] and p[(i+1)//2]:
        c += 1
    x[i] = c

for _ in range(q):
    l, r = map(int, input().split())
    print(x[r] - x[l-1])
n, *p = map(int, open(0).read().split())
s = sum(j - i - max(0, i - j) - max(0, j - i)%2 for i, j in zip(p, p[n:]))
print("NO" if [s >= 0 == s%2 ::2] else "Yes")

### FIXED CODE ###

n, *p = map(int, open(0).read().split())
s = sum(j - i - max(0, i - j) - max(0, j - i)%2 for i, j in zip(p, p[n:]))
print("Yes" if s >= 0 == s%2 else "No")
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])


### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
if n<=x:
    x=n-1
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])
print((lambda x:int(x[1])+(100*(10 - 10 if x[0]>=10 else x[0])))(input().split()))

### FIXED CODE ###

print((lambda x:(int(x[1])+(100*(10 - (10 if int(x[0])>=10 else int(x[0]))))))(input().split()))
import math

data =map(int, raw_input().split(" "))

dx = data[2] - data[0]
dy = data[3] - data[1]

print math.sqrt(dx**2+dy**2)

### FIXED CODE ###

import math

data =map(float, raw_input().split(" "))

dx = data[2] - data[0]
dy = data[3] - data[1]

print math.sqrt(dx**2+dy**2)
# coding: utf-8

N = input()
array1 = input().split()
#array2 = int(array1)
array = list(array1)
chk = 0

if (int(array[0])%2) != 0:
	print("0")
else:
	flg = 0
	mini1 = min(array)
	mini = int(mini1)
	while 1:
		mini = mini/2
		flg +=1
		if mini%2 !== 0:
			break

	print(flg)

### FIXED CODE ###

# coding: utf-8

N = input()
N_list = list(N)
N_count = N_list.count("1")

if N_count == 0:
	print("0")
elif N_count == 1:
	print("1")
elif N_count == 2:
	print("2")
elif N_count == 3:
	print("3")
sa = list(input())
sb = list(input())
sc = list(input())

d = sa[0]

while d !=[]:
    if d == 'a':
        sa = sa[1::]
        d = sa[0]
    elif d == 'b':
        sb = sb[1::]
        d = sb[0]
    else:
        sc = sc[1::]
        d = sc[0]

if len(sa) == 0:
    print('A')
elif len(sb) == 0:
    print('B')
else:
    print('C')

### FIXED CODE ###

sa = list(input())
sb = list(input())
sc = list(input())

d = 'a'
cnta = 0
cntb = 0
cntc = 0
A = len(sa)
B = len(sb)
C = len(sc)

while 1:
    if d == 'a':
        cnta += 1
        if cnta == A+1:
            print('A')
            break
        d = sa.pop(0)
    elif d == 'b':
        cntb += 1
        if cntb == B+1:
            print('B')
            break
        d = sb.pop(0)
    else:
        cntc += 1
        if cntc == C+1:
            print('C')
            break
        d = sc.pop(0)
n,m=map(int,input().split())
path=[[[0]*n]*n]
for i in range(m):
    a,b=map(int,input().split())
    path[a][b]=1
    path[b][a]=1#隣接グラフを作成
visited=[[0]*n]#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(0,n,visited)

### FIXED CODE ###

n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1#隣接グラフを作成
visited=[0]*n#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(dfs(0,visited,n))
N,M,X,Y = map(int, input().split())
num_list = [list(map(int, input().split())) for _ in range(M)]

Z = list(range(X+1,Y+1))

for z in Z:
    if max(num_list[0]) < z and min(num_list[1]) >= z:
        print('No War')
        break
    if z == Z[-1]:
        print('War')

### FIXED CODE ###

N,M,X,Y = map(int, input().split())
num_list = [list(map(int, input().split())) for _ in range(2)]

Z = list(range(X+1,Y+1))

for z in Z:
    if max(num_list[0]) < z and min(num_list[1]) >= z:
        print('No War')
        break
    if z == Z[-1]:
        print('War')
import sys


primes = [2]

def solv(num):
    if num < primes[-1]:
        p1 = filter(lambda x: x < num)[-1]
    else:
        for p in prime_list(num * 2):
            primes.append(p)
            if num < p:
                p2 = p
                break
            else:
                if p < num:
                    p1 = p
    return (p1, p2)


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]



for line in sys.stdin:
    number = int(line)
    p1, p2 = solv(number)
    print ' '.join(map(str, [p1, p2]))

### FIXED CODE ###


import sys


primes = [2]

def solv(num):
    p1 = 0
    p2 = 0
    if num < primes[-1]:
        p1 = filter(lambda x: x < num, primes)[-1]
        lis = filter(lambda x: num < x, primes)
        if lis:
            p2 = lis[0]
    else:
        for p in prime_list(num * 2):
            primes.append(p)
            if num < p:
                p2 = p
                break
            else:
                if p < num:
                    p1 = p
    return (p1, p2)


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]



for line in sys.stdin:
    number = int(line)
    p1, p2 = solv(number)
    print ' '.join(map(str, [p1, p2]))
N,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = 0
for i in a:
    x -= i
    if x => 0:
        b += 1
    else:
        break
print(b)

### FIXED CODE ###

N,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = 0
for i in a:
    x -= i
    if x >= 0:
        b += 1
        N -= 1
    else:
        break
if x == 0:
    print(b)
else:
    if N == 0:
        print(b-1)
    else:
        print(b)
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

a = rr()
b = 0
for　i in a:
  b += int(i)
  b = b%9
if b == 0:
  print('Yes')
else:
  print('No')













### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

a = rr()
b = 0
for i in a:
  b += int(i)
  b = b%9
if b == 0:
  print('Yes')
else:
  print('No')
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

def main():
    N, M = mi()
    A, B = i2(M)

    uf = Uf(N)

    for i in range(M):
        uf.unite(A[i]-1, B[i]-1)

    print(max(uf.count(i) for i in range(N)))
    


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

def main():
    N, M = mi()

    if M == 0:
        print(1)
        return
        
    A, B = i2(M)

    uf = Uf(N)
    for i in range(M):
        uf.unite(A[i]-1, B[i]-1)

    print(max(uf.count(i) for i in range(N)))
    


if __name__ == '__main__':
    main()