Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
from sys import stdin
from collections import Counter
import numpy as np


s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, K = ds_in()
t_list = []
d_list = []
for _ in range(N):
    t, d = ds_in()
    t_list.append(t)
    d_list.append(d)
np_t = np.array(t_list)
np_d = np.array(d_list)

sort_idx = np.argsort(np_d)[::-1][:K]
top_sushi = np_t[sort_idx]
top_score = np_d[sort_idx]
kind = len(set(top_sushi))
point = top_score.sum() + kind**2
point_list = [point]
sushi_counter = Counter(top_sushi)

sushi_set = {k: [] for k in set(t_list)}
for i, j in zip(t_list, d_list):
    sushi_set[i].append(j)
max_sushi = {k: max(sushi_set[k]) for k in set(t_list)}

for s in set(top_sushi):
    max_sushi.pop(s)
max_values = list(max_sushi.values())
max_values.sort(reverse=True)

for sushi, score in zip(top_sushi[::-1], top_score[::-1]):
    if sushi_counter[sushi] > 1:
        sushi_counter[sushi] -= 1
        kind += 1
        point = point - score + max_values.pop(0) + 2*kind - 1
        point_list.append(point)
        if len(max_values) == 0:
            break

print(max(point_list))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from collections import Counter
import numpy as np

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, K = ds_in()
t_list = []
d_list = []
for _ in range(N):
    t, d = ds_in()
    t_list.append(t)
    d_list.append(d)
np_t = np.array(t_list)  # sushi kind
np_d = np.array(d_list)  # sushi value

sort_idx = np.argsort(np_d)[::-1][:K]  # top K value sushi
top_sushi = np_t[sort_idx]
top_score = np_d[sort_idx]
kind = len(set(top_sushi))
point = top_score.sum() + kind**2  # temp max point
point_list = [point]
sushi_counter = Counter(top_sushi)

sushi_set = {k: [] for k in set(t_list)}
for i, j in zip(t_list, d_list):
    sushi_set[i].append(j)
max_sushi = {k: max(sushi_set[k]) for k in set(t_list)}

for s in set(top_sushi):
    max_sushi.pop(s)  # temp max point
max_values = list(max_sushi.values())
max_values.sort(reverse=True)
if len(max_values) > 0:
    for sushi, score in zip(top_sushi[::-1], top_score[::-1]):
        if sushi_counter[sushi] > 1:
            sushi_counter[sushi] -= 1
            kind += 1
            point = point - score + max_values.pop(0) + 2*kind - 1
            point_list.append(point)
            if len(max_values) == 0:
                break

print(max(point_list))
a, b = map(int, input().split())

print(max(o, a-2*b))

### FIXED CODE ###

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

print(max(0, a-2*b))
N=int(input())
X=list(map(int,input().split()))
ans=[]
for i in range(min(X),max(X)):
    goukei = 0
    for j in range(len(X)):
        if i%1==0:
            goukei+=(X[j]-i)**2
    ans.append(goukei)
kotae=set(ans)
print(min(kotae))

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
ans=[]
for i in range(max(X)+1):
    goukei = 0
    for j in range(N):
        if i%1==0:
            goukei+=(X[j]-i)**2
    ans.append(goukei)
kotae=set(ans)
print(min(kotae))
w = list(input())
s = set(w)
ans = 'Yes'

for i in range(len(s)):
  if w.count(s[0]) % 2 == 1:
    ans = 'No'
    break

    print(ans)

### FIXED CODE ###

w = list(input())
s = set(w)
s = list(s)
ans = 'Yes'

for i in range(len(s)):
  if w.count(s[i]) % 2 == 1:
    ans = 'No'
    break

print(ans)
import math
t = int(input())
sum =0
while t>0:
    sum += t%10
    t = int(t/10)

if sum%9==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
t = list((input()))
sum=0
for e in t:
    sum+=int(e)
if sum%9==0:
    print('Yes')
else:
    print('No')
a,b,c=map(int,(input().split())
print(a*b//2)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(a*b//2)
s = input()
print(700+100*(s.count(o)))

### FIXED CODE ###

s = list(input())
print(700+100*(s.count('o')))
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                print(V[i+1],V[i],x)
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input()).rstrip("\n")
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split().rstrip("\n")
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = getInputInt()
data = getInputListInt()
l = len(data)

ans = []

for i in range(l-1, -1, -1):
    cnt = 0
    for j in ans:
        if j % (i+1) == 0:
            cnt += 1
    if data[i] != cnt % 2:
        ans.append(i+1)

if len(ans) == 0:
    print(0)
else:
    print(len(ans))
    print(*ans, sep=" ")




### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    b = [0 for i in range(n)]
    ans = []

    for i in range(n // 2, n):
        if a[i] == 1:
            b[i] = a[i]
            ans.append(i + 1)

    for i in range(n // 2 - 1, -1, -1):
        cnt = 0
        for j in range(i * 2 + 1, n, i + 1):
            cnt ^= b[j]
        if cnt != a[i]:
            b[i] = 1
            ans.append(i + 1)

    tmp = len(ans)
    print(tmp)
    if tmp > 0:
        print(*ans, sep=" ")


if __name__ == '__main__':
    main()
##C
X,N = map(int,input().split())
P = list(map(int,input().split()))
i=0

while X+i<=100:
    if X+i not in P:
        ans1 = X+i
        break
    i += 1
while X-i>=-100:
    if X-i not in P:
        ans2 = X-i
        break
    i += 1
if ans1-X>=X-ans2:
    print(ans2)
else:
    print(ans1)

### FIXED CODE ###

##C
X,N = map(int,input().split())
P = list(map(int,input().split()))
i=0
j = 0
while X+i<=101:
    if X+i not in P:
        ans1 = X+i
        break
    i += 1
while X-j>=-1:
    if X-j not in P:
        ans2 = X-j
        break
    j += 1
if ans1-X>=X-ans2:
    print(ans2)
else:
    print(ans1)
A = input(int)
B = input(int)

print(6-A-B)

### FIXED CODE ###

A = int(input())
B = int(input())

print(6-A-B)
X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    if X<K*D-X:
        ans=X
        for i in range(0,K):
            ans=ans-D
            if ans<0 and (K-i)%2==0:
                ans=ans+D
                break
            elif ans<0 and (K-i)%2==1:
                ans=-ans
                break
    else:
        ans=K*D-X
        for i in range(0,K):
            ans=ans+D
        if ans>0 and (K-i)%2==0:
            ans=-ans+D
            break
        elif ans>0 and (K-i)%2==1:
            ans=ans
            break
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)
S = input()
T = input()

x = T - S

y = len(x)

if y == 1:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

S = input()

T = input()

x = T[0:-1]

if S == x:
    print('Yes')
else:
    print('No')
a,b,c = map(int,raw_input().split())
ans = []
for i in range(a,b+1):
	if c%i == 0:
		ans.append(i)
return ans

### FIXED CODE ###

a,b,c = map(int,raw_input().split())
lst = []
for i in range(a,b+1):
	if c%i == 0:
		lst.append(i)
print len(lst)
from sys import stdin

n = stdin.readline().rstrip().split()[0]
A = [int(x) for x in stdin.readline().rstrip().split()]

s = str(int((sum(A)**2 - sum([a**2 for a in A])) / 2))

if(int(s) < (10**9 + 7)):
    print(int(s))

x = int(s[-9:]) - 7 * int(s[:-9])
if(x < 0):
    print(x + 10**9 + 7)
else:
    print(x)

### FIXED CODE ###

import sys
 
stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))
 
 
def main():
    n = ni()
    A = nl()
    mod = 10 ** 9 + 7
    s = sum(A)
    q = sum([a ** 2 for a in A])
    ans = (((s * s) - q)) // 2
    print(int(ans % mod))
 
 
if __name__ == '__main__':
    main()
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    dp[i+1][j+1]=max(dp[i][j]+(s[i]==t[j]),dp[i+1][j],dp[i][j+1])

ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    ans+=s[i-1]
    rec(i-1,j-1)
  elif dp[i-1][j]>=dp[i][j-1]:
    rec(i-1,j)
  else:
    rec(i,j-1)
rec(ls,lt)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
                                                                                                    
ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    ans+=s[i-1]
    rec(i-1,j-1)
  elif dp[i-1][j]>=dp[i][j-1]:
    rec(i-1,j)
  else:
    rec(i,j-1)
rec(ls,lt)
print(ans[::-1])
n = int(input())
count=0
while n>=5:
  temp=[]
  i=1
  while n>=6**i:
    temp.append(6**i)
    i=i+1
  i=1
  while n>=9**i:
    temp.append(9**i)
    i=i+1
  n=n-max(temp)
  count=count+1
print(count+n)

### FIXED CODE ###

n = int(input())
count=n
for i in range(0,n+1):
  temp=0
  temp6=i
  while temp6>0:
    temp=temp+temp6%6
    temp6=int(temp6/6)
  temp9=n-i
  while temp9>0:
    temp=temp+temp9%9
    temp9=int(temp9/9)
  count=min(count,temp)
print(count)
n = int(input())
s = list(input())

max = 0
for i in range(1,n):
    l = len(set(s[:i]&s[i:]))
    if l > max:
        max = l

print(max)

### FIXED CODE ###

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


max = 0
for i in range(1,n):
    xs = set(s[:i])
    ys = set(s[i:])
    l = len(xs&ys)
    if l > max:
        max = l

print(max)
string=list(input())
if int(string[1]==0):
  c=1
else:
  c=0
a=0
for s in string:
  if int(s)==0 and c==1:
    c-=1
  elif int(s)==0 and c==0:
    c+=1
    a+=1
  elif int(s)==1 and c==0:
	c+=1
  elif int(s)==1 and c==1:
	c-=1
    a+=1
print(a)

### FIXED CODE ###

string=list(input())
if int(string[0])==1:
    c=0
else:
    c=1
a=0
for s in string:
    if int(s)==0 and c==1:
        c-=1
    elif int(s)==0 and c==0:
        c+=1
        a+=1
    elif int(s)==1 and c==0:
        c+=1
    elif int(s)==1 and c==1:
        c-=1
        a+=1
print(a)
while True:
    n,x=map(int,input().split())
    if n==0 and x==0:break
    for i in range(1,n+1):
        for j in range(1,i):
            for k in range(1,j):
                if i+j+k==x:a+=1
    print(a)



### FIXED CODE ###

while True:
    n,x=map(int,input().split())
    a=0
    if n==0 and x==0:break
    for i in range(1,n+1):
        for j in range(1,i):
            for k in range(1,j):
                if i+j+k==x:a+=1
    print(a)
from collections import defaultdict


def scc(g):
    rg = defaultdict(list)
    V = set()
    for u, e in g.items():
        V.add(u)
        for v in e:
            V.add(v)
            rg[v].append(u)


    o = []
    done = set()
    def dfs(u):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            dfs(v)
            done.add(v)
        # o[u] = len(o)
        o.append(u)

    for v in V:
        if v in done:
            continue
        dfs(v)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        done.add(u)
        s = [u]
        vv = []

        while s:
            u = s.pop()
            vv.append(u)
            for v in rg[u]:
                if v in done:
                    continue
                s.append(v)
                done.add(v)
        ans.append(vv)

    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    g = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
    vv = scc(g)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    vv = scc(g)
    for r in vv:
        print(r)


if __name__ == "__main__":
    # test()
    atcoder_practice2_g()


### FIXED CODE ###


from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(N, g, rg):
    V = list(range(N))


    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    g = defaultdict(list)
    rg = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        rg[b].append(a)
    vv = scc(N, g, rg)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    vv = scc(g)
    for r in vv:
        print(r)


if __name__ == "__main__":
    # test()
    atcoder_practice2_g()
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
d[a]=1
for s in(q:=[a:=~w+a*w+b]):
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
istr=input()
for ch in istr:
  if ch == '0':
    c0+=1
  else:
    c1+=1
print(min(c0,c1)*2)
      

### FIXED CODE ###

istr=input()
c0=0
c1=0
for ch in istr:
    if ch == '0':
        c0+=1
    else:
        c1+=1
print(min(c0,c1)*2)
N,D = map(int, input().split())
A = [0] * D
count = 0
sei = 0

for i in range(0,N):
	A[i] = list(map(int, input().split()))
    
for p in range(0,N):
    for q in range(0,N):
        sum = 0
    
        for r in range(0,D):
            sum = sum + (A[p][r]-A[q][r]) ** 2
           
        sum = sum ** 0.5 
        sei = int(sum)
        
        if sum != 0 and sum == sei:
            count = count + 1
      
print(count // 2)

### FIXED CODE ###

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

if D == 1:
  print(N * (N-1) // 2)
else:
  A = [0] * N
  count = 0
  sei = 0

  for i in range(0,N):
	  A[i] = list(map(int, input().split()))
    
  for p in range(0,N):
      for q in range(0,N):
          sum = 0
    
          for r in range(0,D):
              sum = sum + (A[p][r]-A[q][r]) ** 2
           
          sum = sum ** 0.5 
          sei = int(sum)
        
          if sum != 0 and sum == sei:
              count = count + 1
      
  print(count // 2)
#まだ自信をもっと答えられないんだよな
#掛け算じゃなくて最小公倍数や
#デバッグの後消す
import math
a,b,c,d=[int(i) for i in input().split()]
c1=b//c-a//c
if a%c==0:
    c1+=1
d1=b//d-a//d
if a%d==0:
    d1+=1
cd1=b//(c*d//math.gcd(c,d))-a//(c*d//math.gcd(c,d))
if a%(c*d)==0:
    cd1+=1
#print(c1)
#print(d1)
#print(cd1)
print(b-a+1-c1-d1+cd1)


### FIXED CODE ###

#まだ自信をもっと答えられないんだよな
#掛け算じゃなくて最小公倍数や
#デバッグの後消す
import fractions
a,b,c,d=[int(i) for i in input().split()]
c1=b//c-a//c
if a%c==0:
    c1+=1
d1=b//d-a//d
if a%d==0:
    d1+=1
cd1=b//(c*d//fractions.gcd(c,d))-a//(c*d//fractions.gcd(c,d))
if a%(c*d)==0:
    cd1+=1
#print(c1)
#print(d1)
#print(cd1)
print(b-a+1-c1-d1+cd1)
#役立つhttps://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)], dtype="int64")

dp = np.zeros(W + 1, dtype="int64")
for w, v in WV:
    dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    
print(dp[-1])


### FIXED CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3 8
3 3
4 5
5 6
ans 9
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""

"""
N<100, W<10*9
wi<10**9, vi<10**3 
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################
#np.maximum(*arrays) == np.max(np.vstack(*arrays), axis=0)
#(np.maximum(np.array([1,3,2]), np.array([2, 1, 3])) == 
# np.max(np.vstack([np.array([1,3,2]), np.array([2, 1, 3])]), axis=0)).all()
################# MAIN #################

N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)], dtype="int64")
Wsum = np.sum(WV[:, 0])
Vsum = np.sum(WV[:, 1])

dp = np.full(Vsum+1, Wsum, dtype="int64")
for w, v in WV:
    dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    
print(np.where(dp < W+1)[0][-1])