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

N = int(input())
a = [int(input()) for i in range(N)]

pushed = [0]
ans = 0
current = 0
while True:
    ans += 1
    current = a[current] - 1
    if current in pushed:
        ans = -1
        break
    if current == 1:
        break
    pushed.append(current)
print(ans)


### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]

pushed = [False] * N
ans = 0
current = 0
while True:
    ans += 1
    current = a[current] - 1
    if pushed[current]:
        ans = -1
        break
    if current == 1:
        break
    pushed[current] = True
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    if bomb.count([bh - 1,bw - 1]) == 0:
        bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[2,2],[1,1],[1,3]]
hmax = max(set(hcnt))#2
wmax = max(set(wcnt))#1
hmaxindex = [ i for i in range(H) if hcnt[i] == hmax]#[0]
wmaxindex = [ i for i in range(W) if wcnt[i] == wmax]#[0,1,2]
#crosspoint has not bomb
for i in hmaxindex:
    for j in wmaxindex:
        if bomb.count([i, j]) == 0:
            print(hmax + wmax)
            sys.exit()
        else:
            continue
#all crosspoint has bomb
print(hmax + wmax - 1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count = 0
for _ in range(N-1):
    while A[_] > A[_+1]:
        A[_ + 1] = A[_ + 1] + 1
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

i = int(input())
a = list(map(int, input().split()))
ans=[]
for i in range(1,len(a)):
    x = 0
    y = 0
    for n in range(i):
        x += a[n]
    for m in range(i,len(a)):
        y += a[m]
    ans.append(abs(x-y))
print(min(ans))

### FIXED CODE ###

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

s=[]
s.append(0)
l = sum(a)
ans=[]
for i in range(1,n):
    s.append(s[i-1]+a[i-1])
    x = s[i]
    y = l-s[i]
    ans.append(abs(x-y))
print(min(ans))
### BUGGY CODE ###

N, M = map(int, input().split())
prices = list(map(int, input().split(' ')))
for i in range(M):
    prices[prices.index(max(prices))] //= 2

print(sum(prices))

### FIXED CODE ###

import heapq
N, M = map(int, input().split(' '))
prices = list(map(lambda x: x * (-1), map(int, input().split(' '))))

# 優先度付きキューに変換
heapq.heapify(prices)

for i in range(M):
    # 最大のものを半額にしてまたキューに突っ込む
    heapq.heappush(prices, ((heapq.heappop(prices) * (-1)) // 2) * -1)

print(sum(prices) * -1)
### BUGGY CODE ###

s = input()
q = int(input())
a = [list(map(str, input().split())) for i in range(q)]

head = 1

for i in range(q):
    if(a[i][0] == '1'):
        head *= -1
    else:
        if(a[i][1] == '2' and head == 1):
            s = s + a[i][2]
        elif(a[i][1] == '1' and head == -1):
            s = s + a[i][2]    
        else:
            s = a[i][2] + s
if(head == 1):
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

s = input()
q = int(input())
a = [list(map(str, input().split())) for i in range(q)]

head = 1
ss = ''

for i in range(q):
    if(a[i][0] == '1'):
        head *= -1
    else:
        if(a[i][1] == '2' and head == 1):
            s = s + a[i][2]
        elif(a[i][1] == '1' and head == -1):
            s = s + a[i][2]    
        else:
            ss = ss + a[i][2]
if(head == 1):
    print(ss[::-1] + s)
else:
    print(s[::-1] + ss)
### BUGGY CODE ###

n, p = map(int,input().split())
def prime_decomposition(p,n):
    table = []
    i = 2
    while p > 1:
        c = 0
        while p%i == 0:
            p /= i
            c += 1
        if c >= n:
            table.append([i,c//n])
        i += 1
    return(table)
a = prime_decomposition(p,n)
c = 1
for j in range(len(a)):
 c = c*(a[j][0]**a[j][1])
print(c)
 



### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
  print(p)
  exit()
a = 1
for k in range(2,1000001):
  c = 0
  while p%k == 0:
    p = p//k
    c += 1
  a *= k**(c//n)
  if p == 1:
    break
print(a)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

def check(limit, max_training, costs, volumes):
    from math import floor
    remain_training = max_training
    for id, (cost, volume) in enumerate(zip(costs, volumes)):
        if cost * volume <= limit:
            continue
        else:
            lowest_cost = floor(limit / volume)
            remain_training -= (cost - lowest_cost)
        if remain_training < 0:
            return False
    return True


def main():
    n, k = map(int, input().rstrip("\n").split(" "))
    costs = list(map(int, input().rstrip("\n").split(" ")))
    volumes = list(map(int, input().rstrip("\n").split(" ")))

    costs.sort()
    volumes.sort(reverse=True)
    queue = []
    total_cost = 0

    success = False

    max_cost = max([cost * volume for cost, volume in zip(costs, volumes)])
    min_cost = 0

    while (min_cost + 1) < max_cost:
        center_cost = (min_cost + max_cost) // 2
        success = check(center_cost, k, costs, volumes)
        if success:
            max_cost = center_cost
        else:
            min_cost = center_cost
    if check(min_cost, k, costs, volumes):
        print(min_cost)
    else:
        print(max_cost)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def check(limit, max_training, costs, volumes):
    from math import floor
    remain_training = max_training
    for id, (cost, volume) in enumerate(zip(costs, volumes)):
        if cost * volume <= limit:
            continue
        else:
            lowest_cost = floor(limit / volume)
            remain_training -= (cost - lowest_cost)
        if remain_training < 0:
            return False
    return True


def main():
    n, k = map(int, input().rstrip("\n").split(" "))
    costs = list(map(int, input().rstrip("\n").split(" ")))
    volumes = list(map(int, input().rstrip("\n").split(" ")))

    costs.sort()
    volumes.sort(reverse=True)
    queue = []
    total_cost = 0

    success = False

    max_cost = max([cost * volume for cost, volume in zip(costs, volumes)])
    min_cost = 0

    while (min_cost + 1) < max_cost:
        center_cost = (min_cost + max_cost) // 2
        success = check(center_cost, k, costs, volumes)
        if success:
            max_cost = center_cost
        else:
            min_cost = center_cost
    if check(min_cost, k, costs, volumes):
        print(min_cost)
    else:
        print(max_cost)


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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

k = inp()

ans = -1
tmp = 0
for i in range(1000001):
  tmp = (tmp * 10 + 7)
  if tmp % k == 0:
    ans = i+1
    break

print(ans)

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

k = inp()

keta = len(str(k))
ans = -1
tmp = 0
for i in range(1000001):
    tmp = ((tmp + (7 * pow(10,i,k)) % k)) % k
    if tmp == 0:
        ans = i+1
        break

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

S = input()
res = [0 for i in range(len(S))]

for i in range(len(S)):
    a = i
    b = S[i]
    while(True):
        if b == 'R':
            a += 1
            if S[a] != b:
                c = a - i - 1#直前までの移動回数
                rev = a#反対になったマス
                a -= 1 #直前のマス
                break
        else:
            a -= 1
            if S[a] != b:
                c = i - a - 1
                rev = a
                a += 1
                break
    if c%2 == 0:
        res[a] += 1
    else:
        res[rev] += 1
for i,r in enumerate(res):
    if i != len(res) -1 :
        print(r, end = " ")
    else:
        print(r)

### FIXED CODE ###

S = input()
Rnum = S.split('L')
Rnum = [len(i) for i in Rnum if i != '']
Lnum = S.split('R')
Lnum = [len(i) for i in Lnum if i != '']
res = [0]*len(S)
count = 0
for i,r in enumerate(Rnum):
    l = Lnum[i]
    res[r+count-1] = int((r+1)/2) + int(l/2)
    res[r+count] = int(r/2) + int((l+1)/2)
    count += r+l
for i,r in enumerate(res):
    if i!= len(res)-1:
        print(r,end=' ')
    else:
        print(r)
### BUGGY CODE ###

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = float("inf")

N, M, L, *I = map(int, open(0).read().split())
ABC, ST = I[:3 * M], I[3 * M + 1:]

E = [[INF] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a - 1][b - 1] = E[b - 1][a - 1] = c


E = WarshallFloyd(E)

for i in range(N):
    for j in range(N):
        if E[i][j] <= L:
            E[i][j] = 1
        else:
            E[i][j] = INF

E = WarshallFloyd(E)

for s, t in zip(*[iter(ST)] * 2):
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else a)


### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int, input().split())
E = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)

for i in range(N):
    for j in range(N):
        E[i][j] = (E[i][j] <= L)

E = floyd_warshall(E)

INF = float("inf")

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else int(a))
### BUGGY CODE ###

INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

### FIXED CODE ###

INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts [to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    max_d = 0
    stk = []
    stk.append((0,set(),0))
    while stk:
        nxt = []
        n,seen,d = stk.pop()
        res = -1
        if(n in seen):
            continue
        max_d = max(max_d,d)
        for x in gp[n]:
            nxt.append((x,seen.union(set([n])),d+1))
        stk = nxt+stk

    if(max_d==0):
        print(-1)
    else:
        print(max_d)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
def combination_to_index(a,b,n):
    if(b<a):
        a,b = b,a
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts[to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)
            cnts[ind]+=1

    ans = 0
    cnt = 0
    stk = deque()
    stk.append((0,0))
    while stk:
        n,ans = stk.popleft()
        for x in gp[n]:
            cnts[x]-=1
            if(cnts[x]==0):
                stk.append((x,ans+1))
                cnt += 1
    if(cnt!=M):
        print(-1)
    else:
        print(ans)

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=2009,m2=10**9+7,b2=1007):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(ans,min(j-i,rh.LCP(l1=i,l2=j)))
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=sys.stdin.readline
def resolve():
    n=int(input())
    s=input()
    dp=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue # i<j
        if s[i]==s[j]:
            dp[i][j]=dp[i+1][j+1]+1
        else:
            dp[i][j]=0
    ans=0
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue
        ans=max(ans,min(j-i,dp[i][j]))
    print(ans)


resolve()
### BUGGY CODE ###

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

import numpy as np

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

ans = 0
for ele in a:
    m = np.sum(a - 1 == ele)
    s = np.sum(a == ele)
    p = np.sum(a + 1 == ele)
    cnt = m + s + p

    ans = max(ans, cnt)

print(ans)

### FIXED CODE ###

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

from collections import Counter

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

c = Counter(a)
keys = c.keys()

st = set()
for key in keys:
    for i in (-1, 0, 1):
        st.add(key + i)

ans = 0
for x in st:
    cnt = c[x-1] + c[x] + c[x+1]
    ans = max(ans, cnt)

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

n=int(input())
a=[int(input()) for i in range(n)]
adic={}
for i in range(n):
    adic[i]=a[i]

temp=sorted(adic.items(),key=lambda x: x[1],reverse=True)
for i in range(n):
    if i != temp[0][0]:
        print(max(a))
    else:
        print(temp[1][1])


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]

a_sort=sorted(a,reverse=True)

for i in range(n):
    if a_sort[0]==a[i]:
        print(a_sort[1])
    else:
        print(a_sort[0])
### BUGGY CODE ###

import numpy as np
N, Q = list(map(int, input().split()))
S = input()
t = [1 if S[j:j+2] == "AC" else 0 for j in range(N)]
for i in range(Q):
  l, r = list(map(int, input().split()))
  print(int(np.sum(t[l-1:r-1])))

### FIXED CODE ###

import numpy as np
N, Q = list(map(int, input().split()))
S = input()
t = [0] * N
for j in range(1, N):
  t[j] = t[j-1] + 1 if S[j-1:j+1] == "AC" else t[j-1]
for i in range(Q):
  l, r = list(map(int, input().split()))
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

from sys import stdin,stdout

input = stdin.readline
print = stdout.write

n,w=map(int,input().split())

inf= 1e18+5
mx = 1000* n
dp = [inf for x in range(w+1)] *(mx+ 1)

dp[0] = 0

for _ in range(n):
    x,y = map(int,input().split())
    for i in range(mx-y,-1,-1):
        dp[i+y] = min(dp[i+y],dp[i]+x)

for i in range(mx,-1,-1):
    if dp[i] <= w:
        print(str(i))
        break
    
        




### FIXED CODE ###

from sys import stdin,stdout

print = stdout.write
input = stdin.readline
INF = 1e10
n,W = map(int,input().split())

wgt = [0]
val = [0]
for i in range(n):
    w,v = map(int,input().split())
    wgt.append(w)
    val.append(v)

max_val=sum(val)    
dp=[[INF for x in range(max_val+1)] for x in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    vi = val[i];wi = wgt[i]
    for V in range(1,max_val+1):
        if vi<= V:
            dp[i][V] = min(wi+dp[i-1][V-vi],dp[i-1][V])
        else:
            dp[i][V]=dp[i-1][V]
res = 0
for i in range(max_val,-1,-1):
    if dp[n][i] <= W:
        res = i
        break
print(str(res))