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

# coding: utf-8
#Problem Name: Prime Number
#ID: tabris
#Mail: t123037@kaiyodai.ac.jp

while True:
    try:
        n = int(raw_input())
        count = 0
        for i in range(1,n+1):
            List = []
            for j in range(2,int(i**.5)+1):
                List.append(i % j != 0)
            if i != 1 and all(List):
                count += 1
        print count
    except:
        break

### FIXED CODE ###

# coding: utf-8
#Problem Name: Prime Number
#ID: tabris
#Mail: t123037@kaiyodai.ac.jp

__max = 999999
List = [False,True]*(__max/2+1)
List[1] = False
List[2] = True
for i in xrange(3,int(__max**.5)+1,2):
    List[i**2::i] = [False]*len(List[i**2::i])

List = [i for i in xrange(2,__max) if List[i]]

while True:
    try:
        n = int(raw_input())
        print __import__('bisect',fromlist=['bisect_right']).bisect_right(List,n)
    except:
        break
### BUGGY CODE ###

#D
#入力
N,K=map(int,input().split())
P=list(map(int,input().split()))

#処理
#内部関数
def d_1(x):
    t=0
    for i in range(1,x+1):
        t+=i/x
        
    return t

P=[ d_1(i) for i in P]#出る目を期待値に変換

x=sum(P[:K])

for i in range(N-K+1):
    t=sum(P[i:i+K])
    if t>x:
        x=t
        
print(x)
        

### FIXED CODE ###

#D
#モジュール
import numpy as np

#入力
N,K=map(int,input().split())
P=np.array(list(map(int,input().split())))

#諸関数
def pront(X):
    #デバッグ用プリント
    #環境変数としてdebugを確保して、それが1なら内容を出力
    if debug==0:
        print(X)

#デバッグ用
debug=1#0:本番,1:デバッグ中



#処理
pront(P)
#関数
def d_1(p):
    #1~pまででるサイコロの期待値を返す
    return((p+1)/2)
#ここまで

P=list(d_1(P))

pront(P)

X=[0]
for i in range(N):
    if i==0:
        X.append(P[i])
    else:
        X.append(P[i]+X[-1])
result=-1
pront(X)
for i in range(N-K+1):
    cal=X[i+K]-X[i]
    if result<cal:
        result=cal
print(result)
### BUGGY CODE ###

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

pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

for i in set(pot_starts):
    if i in pot_ends:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

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

# n, m = 3, 2
# a = [[1, 2], [2, 3]]

pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

if set(pot_starts).intersection(pot_ends):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                count += 1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k >= 0 and k <= K:
            count += 1

print(count)
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]
x.sort()
z,answer = [],0
for j in x:
	if j not in z and x.count(j) < j : answer += x.count(j)
	elif j not in z and x.count(j) > j: answer += x.count(j)-j
	z.append(j)
print(answer)

### FIXED CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
c = collections.Counter(a)
answer = 0
for i in c.most_common():
	if i[0]>i[1]:
		answer += i[1]
	elif i[0]<i[1]:
		answer += i[1]-i[0]
print(answer)
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N) :
    a = int(input())
    A.append(a)

for i in range(N) :
    sub = A[:i] + A[i+1:]
    print(max(sub))

### FIXED CODE ###

N = int(input())
A = []

for i in range(N) :
    a = int(input())
    A.append((a, i))

A.sort(key=lambda A : A[0], reverse=True)

for i in range(N) :
    if i == A[0][1] :
        print(A[1][0])
    else :
        print(A[0][0])
### BUGGY CODE ###

from bisect import bisect_right

N, M = map(int, input().split())
w = sorted([tuple(map(int, input().split())) for _ in range(N)])
days = [x[0] for x in w]
pays = [x[0] for x in sorted(w[:], key=lambda x: x[1], reverse=True)]
ans = 0
for i in range(M):
    c = bisect_right(days, M-i) - 1
    if c < 0:
        break
    e = c
    for j in range(M-i):
        d = bisect_right(days, M - i - 1) - 1
        e = e if w[e][1] >= w[d][1] else d
    ans += w[e][1]
    del w[e]
    del days[e]

print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(N)]
ans = 0

daylist = [[] for _ in range(10**5)]
for a, b in w:
    daylist[a-1].append(b)

q = []
for i in range(M):
    for b in daylist[i]:
        heapq.heappush(q, -b)
    if q:
        ans += -heapq.heappop(q)
print(ans)
### BUGGY CODE ###

S = input()


ABC = 'ABC'

dp = [0, 0, 0, 0]
dp[3] = 1

for c in reversed(S):
    if c == '?':
        m, m1 = 3, 3
    else:
        m, m1 = 1, 1

    for j in range(3):
        m2 = 1 if c == '?' or c == ABC[j] else 0
        dp[j] = m1 * dp[j] + m2 * dp[j+1]
    dp[3] = m * dp[3]

print(dp[0] % 1000000007)


### FIXED CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)
### BUGGY CODE ###

N = int(input())
search_max = int(N)
 
min_number = 10**12
for x in range(1, search_max + 1):
    if N % x == 0:
        y = N // x
        if x + y < min_number:
         
            min_number = x + y
print(min_number-2)

### FIXED CODE ###

N = int(input())
search_max = int(N**0.5)
 
min_number = 10**12
for x in range(1, search_max + 1):
    if N % x == 0:
        y = N // x
        if x + y < min_number:
         
            min_number = x + y
print(min_number-2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans=0

for i in range(n):
  t=a[i]
  ans+=1
  for j in range(i+1, n):
    if t&a[j] == 0:
      t+=a[j]
      ans+=1
    else:
      break

print(ans)

### FIXED CODE ###

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

t = a[0]
ans = 0
r = 1

for l in range(n):
  while r<n and t^a[r] == t+a[r]:
    t+=a[r]
    r+=1
  if r==l:
    l=r+1
  ans += r-l
  t -= a[l]

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

from collections import deque
h, w = map(int, input().split())
mass = [[ord(i) for i in input()]for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[0] * w for _ in range(h)]
    depth = [[0] * w for _ in range(h)]
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r

    u = 0
    for row in depth:
        u = max(u, max(row))
    return u


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))



### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

import math

def combinations_count(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

n = int(input())
a = list(map(int,input().split()))
n_list = [[] for i in range(n)]
len_list = [0 for i in range(n)]

for i in range(n):
    n_list[a[i]-1].append(i)

for i in range(n):
    if len(n_list[i]) == 0:
        len_list[i] == 0
    elif len(n_list[i]) == 1:
        len_list[i] == 1
    else:
        len_list[i] = combinations_count(len(n_list[i]))

sum_len = sum(len_list)
ans_list = [sum_len for i in range(n)]

for i in range(n):
    if len_list[a[i]-1] == 0:
        continue
    elif len_list[a[i]-1] == 1:
        ans_list[i] = ans_list[i] - 1
    elif len_list[a[i]-1] == 2:
        ans_list[i] = ans_list[i] - 1
    else:
        ans_list[i] = ans_list[i] - len_list[a[i]-1] + combinations_count(len(n_list[a[i]-1]) - 1)

for i in range(n):
    print(ans_list[i])


### FIXED CODE ###

import math

def combinations_count(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

n = int(input())
a = list(map(int,input().split()))
n_list = [0 for i in range(n)]
len_list = [0 for i in range(n)]

for i in range(n):
    n_list[a[i]-1] += 1

sum_len = 0

for i in range(n):
    if n_list[i] == 0:
        len_list[i] == 0
    elif n_list[i] == 1:
        len_list[i] == 1
    else:
        len_list[i] = combinations_count(n_list[i])
    sum_len += len_list[i]

for i in range(n):
    if len_list[a[i]-1] == 0:
        print(sum_len)
    elif len_list[a[i]-1] == 1 or len_list[a[i]-1] == 2:
        print(sum_len - 1)
    else:
        print(sum_len - (n_list[a[i]-1] - 1))
### BUGGY CODE ###

n,k,q=(int(x) for x in input().split())
a=[]
p=[]
for i in range(0,q):
    temp=int(input())
    a.append(temp)
border=-k+q

res = '\n'.join('Yes' if a.count(j+1)> border else 'No' for j in range(0,n))

print(res)


### FIXED CODE ###

n,k,q=(int(x) for x in input().split())
a=[]
p=[0]*n
for i in range(0,q):
    temp=int(input())
    p[temp-1]+=1
border=-k+q

res = '\n'.join('Yes' if p[j]> border else 'No' for j in range(0,n))

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

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    A = []
    A_append = A.append

    cnt = 0


    for i in range(n-1):
        A_append(a[i])
        x = sum(A) + a[i+1]
        if sum(A) > 0 and x > 0:
            y = abs(x)+1
            cnt += y
            a[i+1] -= y

        elif sum(A) < 0 and x < 0:
            y = abs(sum(A) - a[i+1])-1
            cnt += y
            a[i+1] += y

    if sum(a) == 0:
        cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

#D
#入力
S=input()
Q=int(input())
Query=[]
for i in range(Q):
    Query.append(list(input().split()))
    
    
#処理

for i in Query:
    if i[0]=="1":
        S=S[::-1]
    elif i[0]=="2":
        if i[1]=="1":
            S=i[2]+S
        elif i[1]=="2":
            S=S+i[2]
print(S)

### FIXED CODE ###

#D
#入力
S=input()
Q=int(input())
#Query=[]
#for i in range(Q):
#    Query.append(list(input().split()))
    
    
#処理
t=0
b=""
a=""
for j in range(Q):
    i=list(input().split())
    if i[0]=="1":
        t+=1
    elif i[0]=="2":
        if t%2==0:
            if i[1]=="1":
                b=i[2]+b
            elif i[1]=="2":
                a=a+i[2]
        elif t%2==1:
            if i[1]=="1":
                a=a+i[2]
            elif i[1]=="2":
                b=i[2]+b
if t%2==0:
    print(b+S+a)
    
else:
    print(a[::-1]+S[::-1]+b[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

D=int(input())
C=[0]+list(map(int,input().split()))
S=[0]+[[0]+list(map(int,input().split())) for i in range(D)]
T=[0]+[int(input()) for i in range(D)]

ANS=0
LAST=[[0]*27 for i in range(D+1)]
for day in range(1,D+1):
    for j in range(1,27):
        LAST[day][j]=LAST[day-1][j]
    t=T[day]
    ANS+=S[day][t]
    LAST[day][t]=day

    for j in range(1,27):
        ANS-=C[j]*(day-LAST[day][j])

    #print(ANS)

M=int(input())
for tests in range(M):
    d,after_t=map(int,input().split())

    before_t=T[d]

    ANS+=S[d][after_t]-S[d][before_t]

    T[d]=after_t

    for day in range(d,D+1):
        if T[day]!=before_t:
            ANS+=C[before_t]*(day-LAST[day][before_t])
            LAST[day][before_t]=LAST[day-1][before_t]
            ANS-=C[before_t]*(day-LAST[day][before_t])
        else:
            break

    ANS+=C[after_t]*(d-LAST[d][after_t])
    LAST[d][after_t]=d

    for day in range(d+1,D+1):    
        if T[day]!=after_t:
            ANS+=C[after_t]*(day-LAST[day][after_t])
            LAST[day][after_t]=LAST[day-1][after_t]
            ANS-=C[after_t]*(day-LAST[day][after_t])

    print(ANS)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

D=int(input())
C=[0]+list(map(int,input().split()))
S=[0]+[[0]+list(map(int,input().split())) for i in range(D)]
T=[0]+[int(input()) for i in range(D)]

ANS=0
LAST=[[0]*27 for i in range(D+1)]
for day in range(1,D+1):
    for j in range(1,27):
        LAST[day][j]=LAST[day-1][j]
    t=T[day]
    ANS+=S[day][t]
    LAST[day][t]=day

    for j in range(1,27):
        ANS-=C[j]*(day-LAST[day][j])

    #print(ANS)

M=int(input())
for tests in range(M):
    d,after_t=map(int,input().split())

    before_t=T[d]

    ANS+=S[d][after_t]-S[d][before_t]

    T[d]=after_t

    for day in range(d,D+1):
        if T[day]!=before_t:
            ANS+=C[before_t]*(day-LAST[day][before_t])
            LAST[day][before_t]=LAST[day-1][before_t]
            ANS-=C[before_t]*(day-LAST[day][before_t])
        else:
            break

    ANS+=C[after_t]*(d-LAST[d][after_t])
    LAST[d][after_t]=d

    for day in range(d+1,D+1):    
        if T[day]!=after_t:
            ANS+=C[after_t]*(day-LAST[day][after_t])
            LAST[day][after_t]=LAST[day-1][after_t]
            ANS-=C[after_t]*(day-LAST[day][after_t])

    print(ANS)
### BUGGY CODE ###

S = input()
Q = int(input())
query = []
for i in range(Q):
    query.append(list(map(str, input().split())))

for q in query:
    if len(q) == 1:
        S = S[::-1]
    else:
        if int(q[1]) == 1:
            S = q[2] + S
        else:
            S = S + q[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
query = []
for i in range(Q):
    query.append(list(map(str, input().split())))


def start(S, x):
    S = x + S
    return S


def end(S, x):
    S = S + x
    return S


front = ''
back = ''
flg = True
for q in query:
    if len(q) == 1:
        flg = not flg
    else:
        if flg == True:
            if q[1] == '1':
                front = start(front, q[2])
            else:
                back = end(back, q[2])
        else:
            if q[1] == '1':
                back = end(back, q[2])
            else:
                front = start(front, q[2])
else:
    if flg == True:
        print(front + S + back)
    else:
        print(back[::-1] + S[::-1] + front[::-1])
### BUGGY CODE ###

import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
S = [0] * N
S[0] = 0
 
for i in range(1, N):
    value = math.inf
    for step in range(1, K + 1):
        if i - step < 0:
            break
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
    S[i] = value
print(S[N - 1])


### FIXED CODE ###

import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
S = [0] * N
S[0] = 0
 
for i in range(1, N):
    value = math.inf
    for step in range(1, K + 1):
        if i - step < 0:
            break
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
    S[i] = value
print(S[N - 1])
### BUGGY CODE ###

n = int(input())
s = [sorted(input()) for i in range(n)]
cnt = 0
 
for j in range(n-1):
  for k in range(j+1,n):
    if s[j] == s[k]:
      cnt += 1
      
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
cnt_s = Counter([" ".join(sorted(input())) for i in range(n)])
print(sum(v*(v - 1)//2 for v in cnt_s.values()))
### BUGGY CODE ###

n = int(input())
r = 0
p = 2
while n > 1:
    e = 0
    while n%p == 0:
       e += 1
       n /= p
    i = 1
    while e >= i:
        e -= i
        r += 1
        i += 1
    p += 1
print(r)

### FIXED CODE ###

n = int(input())
r = 0
for p in range(2, int(n**0.5)+1):
    e = 0
    while n%p == 0:
       e += 1
       n /= p
    i = 1
    while e >= i:
        e -= i
        r += 1
        i += 1
if n != 1:
    r += 1
print(r)
### BUGGY CODE ###

#create date: 2020-04-19 21:04

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    for i in range(1, n+1):
        print(a.count(i))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-04-19 21:04

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    ans = [0] * n
    for ai in a:
        ans[ai-1] += 1
    for i in ans:
        print(i)

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

n = int(input())
s = input()
black_appered = False
ans = 10**9
count =0
# [BBB...WWW...]の組を抽出する
for i in range(n+1):
    left = s[:i]
    right = s[i:]
    count = left.count('#') + right.count('.')
    ans = min(ans,count)
    # print(left," | ", right," | ", count, ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
black_in_left = 0
white_in_right = s.count('.')
ans = black_in_left + white_in_right

for x in s:
    if x == '#':
        black_in_left += 1
    if x == '.':
        white_in_right -= 1
    cost = black_in_left + white_in_right
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())

P = [int(i) for i in input().split()]

count = 0
for i in range(N):
    if P[i] == np.min(P[:i+1]):
        count += 1
print(count)

### FIXED CODE ###

import numpy as np

N = int(input())

P = [int(i) for i in input().split()]

minimum = P[0]
count = 1
for i in range(1, N):
    if P[i] <= minimum:
        count += 1
        minimum = P[i]

print(count)
### BUGGY CODE ###

from heapq import heappush,heappop
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=[]
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.append(mod-t)
for i in range(N-1,-1,-1):
    print(ans[i])

### FIXED CODE ###

from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

def calc_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()
    return divisors

def div_or_sub(n, k):
    while k <= n:
        if n % k == 0:
            n //= k
        else:
            n -= k
    return n

n = int(input())
cnt = len(calc_divisors(n - 1)) - 1
n_divisors = calc_divisors(n)
for divisor in n_divisors[1:]:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

def calc_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()
    return divisors

def div_or_sub(n, k):
    while k <= n:
        if n % k == 0:
            n //= k
        else:
            n %= k
    return n

n = int(input())
cnt = len(calc_divisors(n - 1)) - 1
n_divisors = calc_divisors(n)
for divisor in n_divisors[1:]:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n, W = map(int, input().split())
dp = [[float("inf")] * (1010 * (n + 1)) for _ in range(n + 1)]

dp[0][0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(i, -1, -1):
        for k in range(v_max + 1):
            dp[j + 1][k + v] = min(dp[j][k] + w, dp[j + 1][k + v])
    v_max += v

ans = 0
for i in range(n + 1):
    for j in range(v_max + 1):
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

### FIXED CODE ###

n, W = map(int, input().split())
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = map(int, input().split())
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)