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

#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#別に誰も10^100なんて数が必要とはいってないのだ
def resolve():
    S=input()
    #シミュレーション真面目にやると|s|^2回必要なのでTLEするよ（乱択でごまかす方法をおもいつきませんでした）
    #状態を圧縮するとシミュレーションできませんか？
    #Sのうち、連続する2文字が”RL”か、文末にだけ1以上がある
    #RLの効果が及ぶところごとに分割しよっかLRの真ん中で分割
    N=len(S)
    sub=[N]#kugiri
    sub2=[]#"RL"のLの位置
    for i in range(N-1):
        cont=()
        if S[i]=="L"and S[i+1]=="R":
            sub.append(i+1)
        if S[i]=="R"and S[i+1]=="L":
            sub2.append(i+1)
    sub.sort()
    #print(sub,sub2)

    ans=[0]*N
    temp=[0,0]
    ind=0
    for i in range(N):
        l=sub2[ind]
        temp[(l-i)%2]+=1
        if i+1 in sub:
            ans[l]+=temp[0]
            ans[l-1]+=temp[1]
            temp=[0,0]
            ind+=1
            
    
    print(*ans)
#%%submit!
resolve()


### FIXED CODE ###

#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#別に誰も10^100なんて数が必要とはいってないのだ
def resolve():
    S=input()
    #シミュレーション真面目にやると|s|^2回必要なのでTLEするよ（乱択でごまかす方法をおもいつきませんでした）
    #状態を圧縮するとシミュレーションできませんか？
    #Sのうち、連続する2文字が”RL”か、文末にだけ1以上がある
    #RLの効果が及ぶところごとに分割しよっかLRの真ん中で分割
    N=len(S)
    sub=[N]#kugiri
    sub2=[]#"RL"のLの位置
    for i in range(N-1):
        cont=()
        if S[i]=="L"and S[i+1]=="R":
            sub.append(i+1)
        if S[i]=="R"and S[i+1]=="L":
            sub2.append(i+1)
    sub.sort(reverse=True)
    #print(sub,sub2)

    ans=[0]*N
    temp=[0,0]
    ind=0
    for i in range(N):
        l=sub2[ind]
        temp[(l-i)%2]+=1
        if i+1 in sub:
            ans[l]+=temp[0]
            ans[l-1]+=temp[1]
            temp=[0,0]
            ind+=1
            sub.pop()
            
            
    
    print(*ans)
    
    
#%%submit!
resolve()
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):

    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(AA,[x,i])
    for j in range(start,end):
        a = heapq.heappop(AA)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 400 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
AA = []
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

H,W = list(map(int,input().split()))

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])

while len(Q)>0:
    i,j=Q.pop()
    M_checked[i][j]=True
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

### FIXED CODE ###


H,W = list(map(int,input().split()))

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[p[0]][p[1]]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)
### BUGGY CODE ###

import sys
import itertools
from math import factorial

input = sys.stdin.readline

def func(l, r):
    num_list = [num for num in range(l, r+1)]
    mod = 0
    mod_min = 2019
    for i, j in itertools.combinations(num_list, 2):
        mod = (i*j % 2019)
        if mod < mod_min:
            mod_min = mod
    print(mod_min)


def main():
    l, r = [int(i) for i in input().split()] 
    func(l, r)
    
# main関数呼び出し
if __name__ == "__main__":
    main() 

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def func(l, r):
    mod_min = float('inf')

    for i in range(l, r):
        for j in range(i+1, r+1):
            mod = (i*j % 2019)

            if mod == 0:
                print(mod)
                exit()     

            elif mod < mod_min:
                mod_min = mod

    print(mod_min)

def main():
    l, r = [int(i) for i in input().split()] 
    func(l, r)
    
# main関数呼び出し
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > (s + 1):
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > (s + 1):
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)
### BUGGY CODE ###

line = input().split(' ')
N = int(line[0])
Y = float(line[1])/10000

num_list = [[float(i), float(j), float(N-i-j)] for i in range(N+1) for j in range(N+1-i)]

for i in num_list:
	if (i[0]+i[1]/2+i[2]/10) == Y:
		print(" ".join(map(lambda x: str(int(x)), i)))
		break
else:
	print('-1 -1 -1')

### FIXED CODE ###

line = input().split(' ')
N = int(line[0])
Y = float(line[1])/10000

num_list = ([i, j, N-i-j] for i in range(N+1) for j in range(N+1-i))

for i in num_list:
	if (i[0]+float(i[1])/2+float(i[2])/10) == Y:
		print(" ".join(map(lambda x: str(int(x)), i)))
		break
else:
	print('-1 -1 -1')
### BUGGY CODE ###

def prime_table(n):
    l = [True for _ in range(n + 1)]
    i = 2
    while i * i <= n:
        j = i + i
        while j <= n:
            l[j] = False
            j += i
        i += 1
    table = [i for i in range(n + 1) if l[i] and i >= 2]
    return table


Q = int(input())
prime_list = prime_table(10 ** 5)
for _ in range(Q):
    count = 0
    l, r = map(int,(input().split()))
    for p in prime_list:
        if l > p:
            continue
        if p > r:
            break
        if p == 2017 or ((lambda x:(x + 1) // 2)(p) in prime_list):
            count += 1
    print(count)


### FIXED CODE ###

#coding:UTF-8

def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


mx = 10 ** 5
p = [0 for _ in range(mx + 1)]
for i in range(3, mx + 1):
    if i == 2017 or (is_prime(i) and is_prime((i + 1) // 2)):
        p[i] = 1
d = [0 for i in range(mx + 1)]
for i in range(3, mx + 1):
    d[i] += p[i] + d[i - 1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(d[r] - d[l - 1])
### BUGGY CODE ###

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

ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque
    
q = deque([(0, 0)])
d = [None] * N
p = [None] * N
while len(q) > 0:
    depth, src = q.popleft()
    d[src] = depth
    for dst in graph[src]:
        if d[dst] == None:
            p[dst] = src
            q.append((depth + 1, dst))

c = [0] * N
for j, (pj, xj) in enumerate(px):
    c[pj - 1] += xj
    
ans = [None] * N
for i in range(N):
    if ans[i] != None: continue
    q = []
    src = i
    while src != None:
        if ans[src] != None:
            q.append((src, ans[src]))
            src = None
        else:
            q.append((src, c[src]))
            src = p[src]
    #
    score = 0
    while len(q) > 0:
        src, score_tmp = q.pop()
        score += score_tmp
        ans[src] = score

print(' '.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    t = list(map(int, input().split()))
    L[i], R[i] = t[0]-1, t[1]-1

a = np.ones(N)
for gate in range(M):
    mask = np.zeros(N)
    mask[L[gate]:R[gate]+1] += 1
    a *= mask

print(int(a.sum()))


### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(lambda x: int(x)-1, input().split())

sum = 0
maxl = max(L)
minr = min(R)
for id in range(N):
    if maxl <= id and id <= minr:
        sum += 1

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

MOD = 10**9+7
l = list(map(int,input().split()))
h,w,a,b = l[0],l[1],l[2],l[3]
def pow(x,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res*x % MOD
        x = x*x % MOD
        n = n >> 1
    return res

def comb(n,k):
    return (fact[n]*inv[k] % MOD)*inv[n-k] % MOD

fact = [1]
inv = [1]
for i in range(h+w):
    fact.append(fact[i]*(i+1) % MOD)
    inv.append(pow(fact[i+1],MOD-2) % MOD)
ans = 0
for i in range(w-b):
    ans = (ans + (comb(h-a+b+i-1,b+i)*comb(w-b-i+a-2,a-1) % MOD)) % MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7
l = list(map(int,input().split()))
h,w,a,b = l[0],l[1],l[2],l[3]
def pow(x,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res*x % MOD
        x = x*x % MOD
        n = n >> 1
    return res

def comb(n,k):
    return (fact[n]*inv[k] % MOD)*inv[n-k] % MOD

fact = [1]*1000000
inv = [1]*1000000

for i in range(h+w):
    fact[i+1]=fact[i]*(i+1) % MOD
inv[h+w] = pow(fact[h+w],MOD-2) % MOD
for i in range(h+w-1,0,-1):
    inv[i] = (i+1)*inv[i+1] % MOD
ans = 0
for i in range(w-b):
    ans = (ans + (comb(h-a+b+i-1,b+i)*comb(w-b-i+a-2,a-1) % MOD)) % MOD
print(ans)
### BUGGY CODE ###

N = int(input())

# 初期化
G = [[] for i in range(10 ** 6 + 1)]  # グラフ
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].append(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)


### FIXED CODE ###

N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)
### BUGGY CODE ###

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

A=sorted(A)
B=[0]*(M-1)

for i in range(len(A)-1):
    B[i]=A[i+1]-A[i]

for i in range(N-1):
    if(len(B)==0):
        print("0")
        exit()
    B.remove(max(B))

print(sum(B))

### FIXED CODE ###

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

A=sorted(A)
B=[0]*(M-1)

for i in range(len(A)-1):
    B[i]=A[i+1]-A[i]

B=sorted(B)
if(N>=M):
    print("0")
    exit()
else:
    print(sum(B[0:M-N]))
### BUGGY CODE ###

N,K,S=map(int,input().split())
P=[]
for i in range(N):
    if i<K:
        P.append(S)
    else:
        if S<10**9:
            P.append(S+1)
        else:
            P.append(1)
ans=''
for i in range(N):
    ans=ans+str(P[i])+' '
print(ans)

### FIXED CODE ###

N,K,S=map(int,input().split())
P=[]
for i in range(N):
    if i<K:
        P.append(str(S))
    else:
        if S<10**9:
            P.append(str(S+1))
        else:
            P.append(str(1))

print(" ".join(P))
### BUGGY CODE ###

from functools import reduce

MOD = 10 ** 9 + 7

_ = int(input())
la = list(map(int, input().split()))


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def addmod(a, b):
    return (a + b) % MOD


l = reduce(lcm, la)
answer = reduce(addmod, (l // a for a in la))
print(answer)


### FIXED CODE ###

from functools import reduce
from math import gcd

MOD = 10 ** 9 + 7

_ = int(input())
la = list(map(int, input().split()))


def inv(a):
    return pow(a, MOD - 2, MOD)


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


def addmod(a, b):
    return (a + b) % MOD


l = reduce(lcm, la) % MOD
answer = reduce(addmod, (l * inv(a) for a in la), 0)
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    def factrize(x):
        f = set()
        for i in range(2,int(x**(1/2))+1):
            if x%i == 0:
                f.add(i)
                while x%i == 0:
                    x //= i
        if x != 1:
            f.add(x)
        return f
    
    base = factrize(a[0])
    union = base
    intersection = base
    flag = True
    for num in a[1:]:
        base = factrize(num)
        if len(union) + len(base) != len(union|base):
            flag = False
        intersection = intersection & base
        union = union | base
    
    if flag:
        print("pairwise coprime")
    else:
        if intersection:
            print("not coprime")
        else:
            print("setwise coprime")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    pr = [0]*(max(a)+1)
    flag = True
    for num in a:
        pr[num] += 1
    for i in range(2, max(a)+1):
        count = sum(pr[i::i])
        if count == N:
            print("not coprime")
            exit()
        elif count > 1:
            flag = False
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

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

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

ans = [0, 0]
ans_abs = 10**200

for i in range(1, N):
    A_1 = sum(A[:i])
    A_2 = sum(A[i:])
    ans_abs = min(ans_abs, abs(A_1 - A_2))

print(ans_abs)

### FIXED CODE ###

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

ans = [0, 0]
ans_abs = 10**200

A_sum = sum(A)
A_1 = 0
A_2 = A_sum

for i in range(N - 1):
    A_1 += A[i]
    A_2 -= A[i]
    ans_abs = min(ans_abs, abs(A_1 - A_2))

print(ans_abs)
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


def knapSack(i,w):
    if i<0:
        return 0
    elif dp[i].get(w)!=None:
        return dp[i][w]
    elif wt[i]>w:
        dp[i][w]=knapSack(i-1,w)
    else:
        dp[i][w]=max(val[i]+knapSack(i-1,w-wt[i]),knapSack(i-1,w))
    return dp[i][w]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
dp=[{} for i in range(n)]
print(knapSack(n-1,w))

### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


def knapSack(V):
    for i in range(n + 1):
        for v in range(V + 1):
            if v == 0:
                K[i][v] = 0
            elif val[i - 1] <= v:
                K[i][v] = min(wt[i - 1] + K[i - 1][v - val[i - 1]], K[i - 1][v])
            else:
                K[i][v] = K[i - 1][v]

    return K[n][V]

n,w=mdata()
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=mdata()
V=100005
K = [[1000000007 for x in range(V + 1)] for x in range(n + 1)]
knapSack(V)
m=0
for i in range(n + 1):
    for v in range(V + 1):
        if 1<=K[i][v]<=w :
            m=max(m,v)
print(m)