Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 6)

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

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


class Tree:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1
            elif (self.depths[u] - self.depths[v]) % 2 == 0:
                return False

        self.colors[u] = self.BLACK

        return True


tree = Tree(g)
if tree.dfs(0):
    black = len([x for x in tree.depths if x % 2])
    white = len([x for x in tree.depths if x % 2 == 0])
    ans = black * white - m

else:
    raise Exception
    ans = n * (n - 1) // 2 - m

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

import sys

sys.setrecursionlimit(10 ** 6)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK

    def bipartite_graph(self, u, c):
        self.colors[u] = c
        for v in self.adj[u]:
            if self.colors[v] == c:
                return False
            if self.colors[v] == self.WHITE and not self.bipartite_graph(v, -c):
                return False

        return True


tree = Tree(g)
if tree.bipartite_graph(0, tree.GRAY):
    black = tree.colors.count(tree.GRAY)
    white = tree.colors.count(tree.BLACK)
    ans = black * white - m

else:
    ans = n * (n - 1) // 2 - m

print(ans)
count_ac=0
count_wa=0
count_tle=0
count_re=0
for i in range(int(input())):
    if input() == "AC":
        count_ac += 1
    elif input() == "WA":
        count_wa += 1
    elif input() == "TLE":
        count_tle += 1
    else:
        count_re += 1
print("AC x "+str(count_wa))
print("WA x "+str(count_ac))
print("TLE x "+str(count_tle))
print("RE x "+str(count_re))

### FIXED CODE ###

count_ac=0
count_wa=0
count_tle=0
count_re=0
n=int(input())
for i in range(n):
    s=input()
    if s == "AC":
        count_ac += 1
    elif s == "WA":
        count_wa += 1
    elif s == "TLE":
        count_tle += 1
    else:
        count_re += 1
print("AC x "+str(count_ac))
print("WA x "+str(count_wa))
print("TLE x "+str(count_tle))
print("RE x "+str(count_re))
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = str(bin(e))
    
    
     
                

         
           




### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
#restoring read network
ans=0
import numpy as np
from scipy.sparse import csr_matrix 
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
mat=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
data=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
        
csr=csr_matrix(mat)
csr=floyd_warshall(csr)
if np.array_equal(csr,data):
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            cnt=0
            for k in range(n):
                if data[i][j]>=data[i][k]+data[k][j]:
                    cnt+=1
            if cnt==2:
                ans+=data[i][j]                
    print(ans)            
else:
    print(-1)

### FIXED CODE ###

n=int(input())

mat=[[0 for i in range(n)] for j in range(n)]
data=[[0 for i in range(n)] for j in range(n)]
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

newmat=warshall_floyd(mat)
if newmat==data:
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans+=data[i][j]*int(all(data[i][j]<data[i][k]+data[k][j] for k in range(i))&all(data[i][j]<data[i][k]+data[k][j] for k in range(i+1,j))&all(data[i][j]<data[i][k]+data[k][j] for k in range(j+1,n)))     
    print(ans)      
else:
    print(-1)
M = map(int,input())
print(48 - M)

### FIXED CODE ###

print(48 - int(input()))
T = input()
X = input()

print(float(T)/float(X))

### FIXED CODE ###

T,X =map(int, input().split())
print(float(T)/float(X))
def countInn(n, L):
  numInn = 1
  mainHurdle = L[0]
  hurdle = L[1]
  for i in range(1, n):
    currentH = L[i]
    if currentH < mainHurdle or currentH < hurdle:
      continue
    numInn += 1
    hurdle = currentH
  print(numInn)
  
n = int(input())
a = list(map(int, input().split()))
countInn(n, a)


### FIXED CODE ###

def countInn(n, L):
  numInn = 1
  mainHurdle = L[0]
  hurdle = mainHurdle
  for i in range(1, n):
    currentH = L[i]
    if currentH < mainHurdle or currentH < hurdle:
      continue
    numInn += 1
    hurdle = currentH
  print(numInn)
  
n = int(input())
a = list(map(int, input().split()))
countInn(n, a)
a, b, c, k = map(int, input().split())

if k = 1:
    print(k)
elif k <= a + b:
    print(k)
else:
    r = k - a - b
    print(a-r)


### FIXED CODE ###

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


if k <= a:
    print(k)
elif k <= a + b:
    print(a)
else:
    r = k - a - b
    print(a-r)
import math
n, k = map(int,input().split())
ans = 0
for i in range(n):
    if i+1 < k:
        must = math.ceil(math.log2(k/(i+1)))
        ans += (1/n)*((0.5)**must)
    else:
        ans += (1/n)
print(ans)
    

### FIXED CODE ###

import math
n, k = map(int,input().split())
ans = 0
for i in range(n):
    if i+1 < k:
        must = math.ceil(math.log2(k/(i+1)))
        ans += (1/n)*((0.5)**must)
    else:
        ans += (1/n)
print(ans)
import math
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
y = []
for i in range(N):
    y.append(x[i + 1] - x[i])
y.sort()
ans = math.gcd(y[0], y[1])
for i in range(2, len(y)):
    ans = math.gcd(ans, y[i])
print(ans)

### FIXED CODE ###

import fractions
N, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0] - X)
for i in range(1, N):
    ans = fractions.gcd(ans, abs(x[i] - X))
print(ans)
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    a = []
    for i in range(H):
        a.append(list(map(int, input().split())))

    moves = []

    for y in range(H):
        for x in range(W - 1):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y][x + 1] += 1
                moves.append((y + 1, x + 1, y + 1, x + 2))
        if y != H - 1:
            if a[y][H - 1] % 2 == 1:
                a[y][H - 1] -= 1
                a[y + 1][H - 1] += 1
                moves.append((y + 1, H, y + 2, H))


    print(len(moves))
    for v in moves:
        print('{} {} {} {}'.format(v[0], v[1], v[2], v[3]))


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    a = []
    for i in range(H):
        a.append(list(map(int, input().split())))

    moves = []

    for y in range(H):
        for x in range(W - 1):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y][x + 1] += 1
                moves.append((y + 1, x + 1, y + 1, x + 2))
        if y != H - 1:
            if a[y][W - 1] % 2 == 1:
                a[y][W - 1] -= 1
                a[y + 1][W - 1] += 1
                moves.append((y + 1, W, y + 2, W))


    print(len(moves))
    for v in moves:
        print('{} {} {} {}'.format(v[0], v[1], v[2], v[3]))


if __name__ == '__main__':
    main()
#入力
S=input()

#処理
l=len(S)
if l==0:
  t=1
else:
  t=0

X="AKIHABARA"
while len(S)!=0:
  if S[0]=="A":
    if S[0]==X[0]:
      S=S[1:]
      X=X[1:]
    else:
      t=1
      break
  else:
    if X[0]=="A":
      X=X[1:]
    else:
      if S[0]==X[0]:
      	S=S[1:]
      	X=X[1:]
      else:
        t=1
        break
        
if t==0:
  print("YES")
else:
  print("NO")
        
      


### FIXED CODE ###

#1
#入力
S=input()


#処理
import re
m=re.fullmatch(r'A?KIHA?BA?RA?',S)

if m==None:
    print("NO")
else:
    print("YES")
s=input()

if s[0] == s[1] and s[1] == s[2] and s[2] == s[3]
    print('Bad')    
else:
    print('Good')

### FIXED CODE ###

s=input()

if s[0] == s[1]:
    print('Bad')
    exit()
if s[1] == s[2]:
    print('Bad')   
    exit()
if s[2] == s[3]:
    print('Bad')
    exit()
else:
    print('Good')
X = int(input())
Y = int(input())
ret = int(X + Y/2 + 0.1)
print(str(ret))

### FIXED CODE ###

X, Y = [int(a) for a in input().split()]
ret = int(X + Y/2 + 0.1)
print(str(ret))
N, K, S = map(int,input().split())

if K=0:
    print(1 for i in range(N))

else:
    ans = [S for a in range(K)]
    ain = [S+1 for a in range(N-K)]
    ans = ans + ain
    print(*ans)


### FIXED CODE ###

N, K, S = map(int,input().split())


ans = [S for a in range(K)]
if S == 10**9:
    ain = [1 for a in range(N-K)]
else:
    ain = [S+1 for a in range(N-K)]
ans = ans + ain
print(*ans)
A = input()
B = input()
if A = "1"or B="1":
	if A = "2"or B="2":
		print("3")
	elif A = "3"or B="3":
		print("2")
elif A = "2"or B="2":
	if A = "3"or B="3":
		print("1")


### FIXED CODE ###

A = input()
B = input()
if A == "1"or B=="1":
	if A == "2"or B=="2":
		print("3")
	elif A == "3"or B=="3":
		print("2")
elif A == "2"or B=="2":
	if A == "3"or B=="3":
		print("1")
N = int(input())
S = int(input())
T = int(input())
for i in N:
    print(S + T)


### FIXED CODE ###

N = int(input())
S, T = map(str,input().split())
for i in range(N):
     print(S[i] + T[i],end="")
n, k = map(int, input().split())

a_list = list(map(int, input().split()))

def print_ans(s):
    if len(s)==0:
        print()
    else:
        ans = str(s[0])
        for val in s[1:]:
            ans = ans + " {}".format(val)
        print(ans)

s = []
count = 0
flag = True
done_list = [[]]
while(flag):
    count += 1
    for a in a_list:
        if a in s:
            s = s[0:s.index(a)]
        else:
            s.append(a)

    if count == k:
        pritn_ans(s)
        exit()

    if s in done_list:
        flag = False
    else:
        done_list.append(s.copy())


loop_num = len(done_list)
s = done_list[ k % loop_num ]
print_ans(s)


### FIXED CODE ###

import bisect

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

ind = [[] for _ in range(2*10**5 + 1)]
for i,num in enumerate(a):
    ind[num].append(i)

for i in range(1,2*10**5 + 1):
    if(ind[i]):
        ind[i].append(ind[i][0] + n)

before = []
cnt = 0
now = a[0]
while(True):
    right = bisect.bisect_right(ind[now], cnt%n)
    cnt += ind[now][right] - ind[now][right-1] + 1
    if(ind[now][right] >= n):
        before.append(ind[now][right-1])
    now = a[cnt%n]
    if(cnt%n == 0):
        break

if(cnt//n==1):
    print('')
    exit()

cyc = k%(cnt//n)

cnt = before[cyc-1]
ans = []
while(cnt < n):
    now = a[cnt]
    right = bisect.bisect_right(ind[now],cnt)
    if(ind[now][right] >= n):
        ans.append(now)
        cnt += 1
    else:
        cnt = ind[now][right] + 1

print(' '.join(map(str,ans)))
A,B = map(int,input().split())
print(int((A * B + 1) / 2))

### FIXED CODE ###

A,B,C = map(int,input().split())
N = C- A- B
if  N > 0:
  if A * B * 4 < N ** 2:
    print("Yes")
  else:
    print("No")
else:
  print("No")
N = int(input())
d = [int(input()) for i in N]
print(set(d))

### FIXED CODE ###

print(len(set([int(input()) for _ in range(int(input()))])))
#逆ポーランド記法(Reverse Polish Notation, RPN)
class RPN():
    def __init__(self):
        self.top = 0
        self.S = []
        self.MAX = 99

    def isEmpty(self):
        return self.top == 0

    def isFull(self):
        return self.top >= self.MAX - 1

    def push(self,x):
        if self.isFull():
            raise ValueError("オーバーフロー")
        self.top+=1
        self.S.append(x)

    def pop(self):
        if self.isEmpty():
            raise ValueError("アンダーフロー")
        self.top-=1
        #print("self.top:{}".format(self.top))
        #print("S:{}".format(self.S))
        return self.S.pop(self.top)


X = input().split(" ")
rpn = RPN()
for x in X:
    #print(x)
    if x.isnumeric():
        #print("num")
        rpn.push(x)
    else:
        #print("dig")
        num_2 =rpn.pop()
        num_1 =rpn.pop()
        res = eval(str(num_1) + x + str(num_2))
        rpn.push(res)

print(rpn.pop())


### FIXED CODE ###

#逆ポーランド記法(Reverse Polish Notation, RPN)
class RPN():
    def __init__(self):
        self.top = 0
        self.S = []
        self.MAX = 100

    def isEmpty(self):
        return self.top == 0

    def isFull(self):
        #return self.top >= self.MAX - 1
        return self.top >= self.MAX

    def push(self,x):
        if self.isFull():
            raise ValueError("オーバーフロー")
        self.top+=1
        self.S.append(x)

    def pop(self):
        if self.isEmpty():
            raise ValueError("アンダーフロー")
        self.top-=1
        #print("self.top:{}".format(self.top))
        #print("S:{}".format(self.S))
        return self.S.pop(self.top)


X = input().split(" ")
rpn = RPN()
for x in X:
    #print(x)
    if x.isnumeric():
        #print("num")
        rpn.push(x)
    else:
        #print("dig")
        num_2 =rpn.pop()
        num_1 =rpn.pop()
        res = eval(str(num_1) + x + str(num_2))
        rpn.push(res)

print(rpn.pop())
x, y = map(int,input().split())

grpup_1 = [1, 3, 5, 7, 8, 10, 12]
group_2 = [4, 6, 9, 11]
group_3 = [2]

groups = [group1, group_2, group_3]

for group in groups:
    if x, y in group:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

x, y = map(int,input().split())

group_1 = [1, 3, 5, 7, 8, 10, 12]
group_2 = [4, 6, 9, 11]
group_3 = [2]

groups = [group_1, group_2, group_3]

for group in groups:
    if x in group and y in group:
        print("Yes")
        break
    else:
        None
    if group == group_3:
        print("No")
A,B,H,M=map(int,input().split())
x=360*(H+M/60)/12-360*M/60
cos=math.cos(math.radians(x))
C = A**2 + B**2 - 2*A*B*(cos)
print(C**0.5)

### FIXED CODE ###

import math
A,B,H,M=map(int,input().split())
x=360*(H+M/60)/12-360*M/60
cos=math.cos(math.radians(x))
C = A**2 + B**2 - 2*A*B*(cos)
print(C**0.5)
w = sorted(input())
ret = 'Yes'
for i in range(0, len(w), 2):
    if w[i] != w[i+1]:
        ret = 'No'
        break
print(ret)

### FIXED CODE ###

w = sorted(input())
ret = 'Yes'
if len(w) % 2 == 0:
    for i in range(0, len(w)-1, 2):
        if w[i] != w[i+1]:
            ret = 'No'
            break
else:
    ret = 'No'
print(ret)
import numpy as np
N = int(input())
pos = []
for i in range(N):
    pos.append(list(map(int, input().strip().split())))
pos = np.array(pos)
tmp_index = np.arange(N)
xx, yy = np.meshgrid(tmp_index, tmp_index)
distances = np.linalg.norm(pos[xx]-pos[yy], axis=2)

print(distances.mean()*N)

### FIXED CODE ###

r = int(input().strip())
print(r**2)
a,b,c = map(int,input().split())
ans="Yes"

if a=b=c or (a != b and b != c):
  ans = "No"
  
print(ans)

### FIXED CODE ###

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

if a==b and b==c or (a != b and b != c and c != a):
  ans = "No"
  
print(ans)
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    if memo[k]:
        bc, ret = memo[k]
    else:
        bc = np.bincount(A)
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = test(k)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    s = 0
    ret = []
    for a in it:
        s += a
        ret.append(s)
    return ret


C = [0] * (N + 1)
for a in A:
    C[a] += 1
C.sort()
cs = list(reversed(cumsum(reversed(C))))


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    # S = N
    # i = 1
    # while i < k:
    #     # 最大値は毎回取ることにしてもう見ない
    #     S -= C[-i]
    #     cnt = S // (k - i)
    #     max_c = C[-i - 1]
    #     if max_c <= cnt:
    #         return cnt
    #     i += 1

    ng = 0
    ok = k
    while abs(ng - ok) > 1:
        i = (ng + ok) // 2
        s = N - cs[-i]
        cnt = s // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            ok = i
        else:
            ng = i
    if ok < k:
        i = ok
        s = N - cs[-i]
        return s // (k - i)
    else:
        return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')
x = input()
x = input()
if x == 0:
    print(1)
elif x == 1:
    print(0)

### FIXED CODE ###

x = int(input())
if x == 0:
    print(1)
elif x == 1:
    print(0)
a,b,t = map(int, input())

print(int((t+0.5)/a*b))

### FIXED CODE ###

a,b,t = map(int, input().split())
 
print((t//a)*b)
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
S = P
T = Q
S.sort()
T.sort()
minimum = (S[0]+T[0])
K = 10**9
for i in range(M):
    x,y,c = map(int,input().split())
    S = P[x-1]+Q[y-1]-c
    if S=<K:
        if S <= 0:
            K = 0
        else:
            K = S
if minimum>K:
    print(K)
else:
    print(minimum)

### FIXED CODE ###

A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
K = min(a)+min(b)
X = 10**9
for i in range(M):
    x,y,c = map(int,input().split())
    S = a[x-1]+b[y-1]-c
    if S<X:
        X = S
if X<K:
    print(X)
else:
    print(K)
x = [input().split() for i in range(3)]
N = int(input())
b = [int(input()) for n in range(N)]
l = [[0]*3, [0]*3, [0]*3]
for val in b:
    for i in range(3):
        for j in range(3):
            print(val)
            if val == int(x[i][j]):
                l[i][j] = 1
if l[0][0] + l[0][1] + l[0][2] == 3:
    print('Yes')
elif l[1][0] + l[1][1] + l[1][2] == 3:
    print('Yes')
elif l[2][0] + l[2][1] + l[2][2] == 3:
    pritn('Yes')
elif l[0][0] + l[1][0] + l[2][0] == 3:
    print('Yes')
elif l[0][1] + l[1][1] + l[2][1] == 3:
    print('Yes')
elif l[0][2] + l[1][2] + l[2][2] == 3:
    print('Yes')
elif l[0][0] + l[1][1] + l[2][2] == 3:
    print('Yes')
elif l[0][2] + l[1][1] + l[2][0] == 3:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

x = [input().split() for i in range(3)]
N = int(input())
b = [int(input()) for n in range(N)]
l = [[0]*3, [0]*3, [0]*3]
for val in b:
    for i in range(3):
        for j in range(3):
            if val == int(x[i][j]):
                l[i][j] = 1
if l[0][0] + l[0][1] + l[0][2] == 3:
    print('Yes')
elif l[1][0] + l[1][1] + l[1][2] == 3:
    print('Yes')
elif l[2][0] + l[2][1] + l[2][2] == 3:
    print('Yes')
elif l[0][0] + l[1][0] + l[2][0] == 3:
    print('Yes')
elif l[0][1] + l[1][1] + l[2][1] == 3:
    print('Yes')
elif l[0][2] + l[1][2] + l[2][2] == 3:
    print('Yes')
elif l[0][0] + l[1][1] + l[2][2] == 3:
    print('Yes')
elif l[0][2] + l[1][1] + l[2][0] == 3:
    print('Yes')
else:
    print('No')
# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, n, w))

### FIXED CODE ###

# E Knapsack 2

from collections import deque

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(MAX_V):
        if j-_v < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-_v]+_w)

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = i
print(ans)