Harryxun/stf_run huggingface dataset:
n,k = map(int, input().split())
s = input()
cnt = 0
init = (s[0]=='1')
h=[1]
h_cnt = 0

for i in range(1,n):
    if(s[i]!=s[i-1]):
        h_cnt+=1
        h.append(1)
    else:
        h[h_cnt]+=1

h_cnt+=1

zero_num = 0
ans = 0

if(init): #start with 1
    zero_num = h_cnt//2;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2+1])
        ans = sum_0
        h = h +[0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

else: #start with 0
    zero_num = h_cnt//2 +1;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2])
        ans = sum_0
        h = [0] + h +[0]
        for j in range(0,zero_num-k):#j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
s = input()
cnt = 0
init = (s[0]=='1')
h=[1]
h_cnt = 0

for i in range(1,n):
    if(s[i]!=s[i-1]):
        h_cnt+=1
        h.append(1)
    else:
        h[h_cnt]+=1

h_cnt+=1

zero_num = 0
ans = 0

if(init): #start with 1
    zero_num = h_cnt//2;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2+1])
        ans = sum_0
        h = h +[0,0,0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

else: #start with 0
    zero_num = h_cnt//2 +1;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2])
        ans = sum_0
        h = [0] + h +[0,0,0]
        for j in range(0,zero_num-k):#j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

print(ans)
import math
from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

n, m = map(int, input().split())
A = list(map(lambda x: int(x) // 2, input().split()))

F = set()
for a in A:
    F.add(f(a))
if(len(F) != 1):
    print(0)
    exit()

l = reduce(lcm, A)
ans = 0 if (l == 0) else (- (- (m // 2) // l))
print(ans)

### FIXED CODE ###

from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

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

n, m = map(int, input().split())
A = list(map(lambda x: int(x) // 2, input().split()))

l = reduce(lcm, A, 1)
for a in A:
    if((l // a) % 2 == 0):
        print(0)
        break

else:
    ans = (m // l +1) // 2
    print(ans)
def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
arr_sum = sum(S) #% divisor
arr_ssq = arr_sum*arr_sum % divisor
isq_sum = 0
for i in range(n):
  isq_sum += S[i]*S[i] #% divisor
  
#isq_sum = isq_sum % divisor
tot = (arr_ssq - isq_sum)//2 % divisor

print(tot)

### FIXED CODE ###

D,T,S = [int(n) for n in input().split()]

if D/S <= T:
  print("Yes")
else:
  print("No")
#agc007a

h,w=map(int(raw_input())
cnt=0
for i in range(h):
 cnt+=raw_input().count('#')
if cnt==h+w-1
 print 'Possible'
else:
 print 'Impossible'


### FIXED CODE ###

#agc007a

h,w=map(int,raw_input().split())
cnt=0
for i in range(h):
 cnt+=raw_input().count('#')
if cnt==h+w-1:
 print 'Possible'
else:
 print 'Impossible'
hoge = {}
for i in range(100):
    hoge[i] = i**5
for i in range(100):
    hoge[-i] = -i**5
x = int(input())
for i in hoge.items():
    for j in hoge.items():
        if i[1] - j[1] == x:
            print(i[0], j[0])
            return

### FIXED CODE ###

hoge = {}
for i in range(1000):
    hoge[i] = i**5
for i in range(1000):
    hoge[-i] = -i**5
x = int(input())
for i in hoge.items():
    for j in hoge.items():
        if i[1] - j[1] == x:
            print(i[0], j[0])
            break
    else:
        continue
    break
N,M=map(int,input().split())
high_list=list(map(int,input().split()))
pathlist=[]
for i in range(M):
    pathlist.append(list(map(int,input().split())))
waylist=[0]*N
ans=0
#i行目にi番目から行ける展望台をすべて入れる
for n in range(1,N+1):
    for m in pathlist:
        if(n in m):#もし経路に入っていたら
            if(m[0]==n):#自身じゃない方の高さを代入
                if(high_list[n-1]>high_list[m[1]-1]):
                    ans=ans+1
            else:
                if(high_list[n-1]>high_list[m[0]-1]):
                    ans=ans+1
print(ans)




### FIXED CODE ###

x=input()
print('ARC' if x == 'ABC' else 'ABC')
a,b,x=map(int,input().split())
n=b-a+1
l=[0]*(n+1)
init=a
for i in range(1,n+1):
    if init%x==0:
        l[i]=l[i-1]+1
    else:
        l[i]=l[i-1]
    init+=1
    
print(l[-1]-l[0])

### FIXED CODE ###

#48-B
a,b,x=map(int,input().split())
b_count=b//x
a_count=(a-1)//x
print(b_count-a_count)
a,b=map(int, input().split(" "))
b *= 100
print(a*b/100)

### FIXED CODE ###

from decimal import *
a,b = map(Decimal, input().split())
print(int(a*b))
from collections import deque
S = [ord(a)-97 for a in raw_input()]
N = len(S)
for c in xrange(26):
	ls = deque()
	for i in xrange(N-1):
		if S[i] == c:
			l = i
			break
	else:
		continue
	cnt = 1
	for r in xrange(l+1,N):
		if S[r] == c:
			cnt += 1
			ls.append(r)
			if cnt * 2 > r - l + 1:
				print l+1,r+1
				quit()
		else:
			if cnt * 2 < r - l + 1:
				l = ls.popleft()
				cnt -= 1
print -1,-1

### FIXED CODE ###

from collections import deque
S = [ord(a)-97 for a in raw_input()]
N = len(S)
for c in xrange(26):
	L = deque()
	for i in xrange(N-1):
		if S[i] == c:
			l = i
			break
	else:
		continue
	cnt = 1
	lenL = 0
	for r in xrange(l+1,N):
		if S[r] == c:
			cnt += 1
			L.append(r)
			lenL += 1
			if cnt * 2 > r - l + 1:
				print l+1,r+1
				quit()
		while cnt * 2 < r - l + 1 and lenL > 0:
			l = L.popleft()
			lenL -= 1
			cnt -= 1
print -1,-1
a,b=[i for i in input().split()]
if a<10 and b<10:
    print(a*b)
else:
    print(-1)

### FIXED CODE ###

a,b=[int(i) for i in input().split()]
if 0<a<10 and 0<b<10:
    print(a*b)
else:
    print(-1)
x = input()
li = x.split()
age = li[0]
m = li[1]
if(age <= 5):
  print(0)
elif(age <= 12):
  printf(m / 2)
else:
  print(m)

### FIXED CODE ###

x = input()
li = x.split()
age = int(li[0])
m = int(li[1])
if(age <= 5):
  print(0)
elif(age <= 12):
  print(int(m / 2))
else:
  print(m)
N=input()
c=0
for i in len(N):
  c+=intN[i]
if c%9==0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N=input()
c=0
for i in range(len(N)):
  c+=int(N[i])
if c%9==0:
  print("Yes")
else:
  print("No")
a,b,c=input().split()
if b*c>=a:
  print ("Yes")
else:
  print("No")


### FIXED CODE ###

a,b,c=[int(a) for a in input().split()]
if b*c>=a:
  print ("Yes")
else:
  print("No")
n,x = map(int, input().split())
if n != x:
  print("No")
else:
  print("Yes")
  for i in range(1, 2 * n):
    print(i)


### FIXED CODE ###

n = int(input())
a = input()
b = input()

for i in range(n):
  if i == 0:
    if a == b:
      print(n)
      exit()
  if a[i:] == b[:-i]:
    print(n+i)
    exit()
print(n*2)
a=int(input())
b=int(input())
c=b%a
d=b//a
if c!=0:
    d+=1

print(d)

### FIXED CODE ###

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

for n in range(0,20):
    if n*(a-1)>=b-1:
        break

print(n)
for i in range(5):
  L[i]=int(input())
  
k=int(input())

for i in range(4):
  if L[i+1]-L[i]>k:
    print(':(')
    break
  
  if i=3:
    print(Yay!)
  

### FIXED CODE ###

import sys
L=[0 for i in range(5)]
for i in range(5):
  L[i]=int(input())
  
k=int(input())

for i in range(4):
  for j in range(i+1,5):
    if L[j]-L[i]>k:
      print(':(')
      sys.exit()
  
    if i==2 and j==3:
      print('Yay!')
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]*(nn+1)
    pb = [1]*(nn+1)
    for i in range(nn):
        u1 = G[v][i]
        u2 = G[v][-i-1]
        pf[i+1] = pf[i]*(dp[(v, u1)]+1)
        pb[i+1] = pb[i]*(dp[(v, u2)]+1)
        pf[i+1] %= M
        pb[i+1] %= M
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans))) 

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(100000)
 
 
def dfs1(v, p):
    val = 1
    pre_mul = [1]
    rev_mul = []
    for c in links[v]:
        if c == p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res = 1 + dfs1(c, v)
        val *= res
        val %= m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v] = val
    for i in range(len(rev_mul) - 2, -1, -1):
        rev_mul[i] *= rev_mul[i + 1]
        rev_mul[i] %= m
    rev_mul.append(1)
    pre_muls[v] = [pre_mul, rev_mul]
    return val
 
 
def dfs2(v, p, a):
    dp[v] = dp[v] * a % m
    pmv = pre_muls[v]
    for i, c in enumerate(links[v]):
        if c == p:
            continue
        pmc = pmv[0][i] * pmv[1][i + 1] % m
        pmc = pmc * a % m
        dfs2(c, v, pmc + 1)
 
 
n, m = map(int, input().split())
links = [[] for _ in range(n)]
dp = [0 for _ in range(n)]
pre_muls = [None for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].append(y)
    links[y].append(x)
dfs1(0, None)
dfs2(0, None, 1)
print('\n'.join(map(str, dp)))
import copy
N = int(input())
A = list(map(int, input().split()))

a_types = set(A)

count_dict = [0] * N
for each in A:
    count_dict[each] = A.count(each)

all_types = 0
for value in count_dict:
    all_types += value * (value - 1) // 2

# result_dict = {}
# for each in a_types:
#     result_dict[each] = all_types - count_dict[each] + 1

for a in A:
    print(all_types - count_dict[a] + 1)

### FIXED CODE ###

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

c = [0]*n

for i in range(n):
    c[a[i]-1] = c[a[i]-1] + 1
    
total = 0
for x in c:
    total = total + x*(x-1)//2

for i in range(n):
    print(total - c[a[i]-1] + 1)
import math
A, B = [int(i) for i in input().split(' ')]
gcd = math.gcd(A, B)
print(int(A*B/gcd))

### FIXED CODE ###

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

A, B = [int(i) for i in input().split(' ')]
gcd_ = gcd(A, B)
print(int(A*B/gcd_))
n,n1=input().split()
a=n
b=n1
S=a*b
L=(2*a)+(2*b)
print(S' 'L)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
a=map(int(input()))
print(((a[1]-1)**(a[0]-1))*a[1])

### FIXED CODE ###

a=list(map(int,input().split()))
print(((a[1]-1)**(a[0]-1))*a[1])
import math
import fractions


def make_prime_and_deleted_by_list(n):
    prime_list = [i for i in range(2, n+1)]
    deleted_by_list = [i for i in range(n+1)]
    pi = 0
    target_prime = prime_list[pi]
    while(target_prime < math.sqrt(n)):
        old_prime_list = prime_list.copy()
        prime_list = prime_list[:pi+1]
        for i in old_prime_list:
            if i % target_prime == 0:
                deleted_by_list[i] = target_prime
            else:
                if i > prime_list[pi]:
                    prime_list.append(i)
        pi += 1
        target_prime = prime_list[pi]
    return prime_list, deleted_by_list

def make_factor_list(n, deleted_by_list, factor_list):
    if n == 1:
        return factor_list
    else:
        factor = deleted_by_list[n]
        factor_list.append(factor)
        return make_factor_list(int(n/factor), deleted_by_list, factor_list)

def calc_gcd(As):
    ans = As[0]
    for i in range(1, len(As)):
        ans = fractions.gcd(ans, As[i])
    return ans
        
N = int(input())
As = list(map(int, input().split()))
_, d = make_prime_and_deleted_by_list(max(As))

As_factor_list = []
for A in As:
    As_factor_list.extend(set(make_factor_list(A, d, [])))

if len(set(As_factor_list)) == len(As_factor_list):
    print("pairwise coprime")

else:
    if calc_gcd(As) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

if True:
    N = int(input())
    As = list(map(int, input().split()))

    maxA = 10**6 + 6
    c = [0] * (maxA+1)
    for A in As:
        c[A] += 1
    isPrime = True
    cnt = 0
    for i in range(2, maxA+1):
        cnt = sum(c[i::i])
        if cnt == N:
            # Asはすべてiの約数
            print("not coprime")
            exit()
        if cnt >= 2:
            isPrime = False
        
    else:
        if isPrime:
            print("pairwise coprime")
        else:
            print("setwise coprime")
K = int(input())
S = input()

str = S

#if same, no change
if lens(S) == k:
                         print(str)

else:
         print (str[0:K] +"...")


### FIXED CODE ###

#K input for the range of S
K = int(input())
#input of lowercase english letters
S = input()
if len(S) > K:
    print(S[:K] + "...")
else:
    print(S)
def dfs(v, p, c):
    for u, w in tree[v]:
        res[v] = c
        if u == p:
            continue
        else:
            if w % 2 == 0:
                dfs(u, v, c)
            else:
                dfs(u, v, c + 1)


n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    tree[u - 1].append([v - 1, w])
    tree[v - 1].append([u - 1, w])

res = [0 for _ in range(n)]
dfs(0, -1, 0)

for i in res:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)


n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    tree[u - 1].append((v - 1, w))
    tree[v - 1].append((u - 1, w))

dist = [0 for _ in range(n)]
dfs(0, -1, dist)

for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)
n=int(input())
a=list(map(int,input(),split()))

for i in range(n):
	v=a[i]
	j=i-1
	while j>=0 and a[j]>v:
		a[j+1]=a[j]
		j=j-1
	a[j+1]=v
	print(' '.join(map(str,a)))



### FIXED CODE ###

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

for i in range(n):
	v=a[i]
	j=i-1
	while j>=0 and a[j]>v:
		a[j+1]=a[j]
		j=j-1
	a[j+1]=v
	print(' '.join(map(str,a)))
n = input()
inf = 1000000000
M = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
  str = raw_input().split()
  u = int(str[0])
  k = int(str[1])
  for j in range(k):
    v = int(str[2+j])
    c = int(str[3+j])
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]

d[0] = 0
color[0] = 1

while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
    print minv
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])

### FIXED CODE ###

n = input()
inf = 1000000000
M = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  for j in range(k):
    v = str[2+2*j]
    c = str[3+2*j]
    M[u][v] = c
d = [inf for i in range(n)]
color = [0 for i in range(n)]
 
d[0] = 0
color[0] = 1
 
while 1:
  minv = inf
  u = -1
  for i in range(n):
    if minv>d[i] and color[i]!=2:
      u = i
      minv = d[i]
  if u == -1:
    break
  color[u] = 2
  for v in range(n):
    if color[v]!=2 and M[u][v]!=inf:
      if d[v]>d[u]+M[u][v]:
        d[v] = d[u] + M[u][v]
        color[v] = 1
for i in range(n):
  if d[i]==inf:
    print '%d -1' % i
  else:
    print '%d %d' % (i, d[i])
S, T = map(str, input().split())

    print(T + S )

### FIXED CODE ###

S, T = map(str, input().split())

print(T + S )
while True:
    num = [int(i) for i in input().split("")]
    if num[0] == 0:
        break
    print(sum(num), end = "\n")
    
     

### FIXED CODE ###

while True:
    x = input()
    if x == "0":
        break
    num = [int(i) for i in x]
    print(sum(num))
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start+1)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    for i in range(L):
        loop[i] = loop[i-1] + A[start+i]

    res = 0

    if N >= start:
        res += straight[-1]
        N -= start
    else:
        res += straight[N-1]
        N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M+2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


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

    A = [-1 for i in range(M+2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()
n=int(input())
h=list(map(int,input().split()))
cnt=1
for i in range(1,n+1):
	if h[i]>=h[0]:
		cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
cnt=1
maxh=h[0]
for i in range(1,n):
	if maxh<=h[i]:
		maxh=h[i]
		cnt+=1
print(cnt)
import math
r = int(input())
S = math.pi * r * r
L = 2 * math.pi * r
print("{0} {1}".format(S, L))

### FIXED CODE ###

import math
r = input()
r = float(r)
S = math.pi * r * r
L = 2 * math.pi * r
print("{0} {1}".format(round(S,6), round(L,6)))
a = int(input())
b = input()
if len(a) < b:
    print(b[:a]+'...')
else:
    print(b)

### FIXED CODE ###

a = int(input())
b = input()
if len(b) > a:
    print(b[:a]+'...')
else:
    print(b)
n = int(input())

nums = list(range(1,n+1))
print(sum(nums[:-1]))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
import numpy as np
N, W = map(int, input().split())

dp = np.zeros(W + 1, int)

for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])

print(dp[-1])


### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())

dp = np.full(N * 1001, W + 10000)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[:-v] + w, dp[v:])

ans = np.max(np.where(dp <= W))
print(ans)
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())




n,m=mi()
if(n==m):
    print("Yes")
else:
    print('No')

### FIXED CODE ###

# from math import ceil,sqrt,log,gcd
# def ii():return int(input())
# def si():return input()
# def mi():return map(int,input().split())
# def li():return list(mi())




n,m=map(int,input().split())
if(n==m):
    print("Yes")
else:
    print('No')
input()
v = [0,0,0]
ans = 1
MOD = 1000000007
for a in map(int,input().split()):
    c = v.count(a)
    ans *= c
    ans %= MOD
    v[v.index(a)] += 1
print(ans)

### FIXED CODE ###

input()
v = [0,0,0]
ans = 1
MOD = 1000000007
for a in map(int,input().split()):
    c = v.count(a)
    ans *= c
    ans %= MOD
    if ans == 0:
        break
    v[v.index(a)] += 1
print(ans)
x=input()
a=input()
b=input()

c=x-a
print(c%b)

### FIXED CODE ###

x=int(input())
a=int(input())
b=int(input())

c=x-a
print(c%b)
n,m=map(int,input().split())
A=list(map(int,input().split()))
s=sorted(A,reverse=True)[m-1]
t=sum(A)//(4*m)+1
if s>=t:
    ans='Yes'
else:
    ans='No'
print(ans)

### FIXED CODE ###

X,Y,Z=input().split()
N=[X,Y,Z]
print(N[2],N[0],N[1])
H,W = map(int,input().split())
figure = [input() for _ in range(H)]
D = [(1,0), (-1, 0), (0,1), (0,-1)]

for h in range(H):
  for w in range(W):
    if figure[h][w] == '#':
      for dh,dw in D:
        nh, nw = h+dh, w+dw
        if not (0 <= nh <=H and 0 <= nw <= W):
          continue
        if figure[nh][nw] == '#':
          break
      else:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

H,W = map(int,input().split())
figure = [input() for _ in range(H)]
D = [(1,0), (-1, 0), (0,1), (0,-1)]

for h in range(H):
  for w in range(W):
    if figure[h][w] == '#':
      for dh,dw in D:
        nh, nw = h+dh, w+dw
        if not (0 <= nh <H and 0 <= nw < W):
          continue
        if figure[nh][nw] == '#':
          break
      else:
        print('No')
        exit()
print('Yes')
I=lambda:list(map(int,input().split()))
n,m=I()
e=[(I()[0],[2**(n-i)for i in I()])for _ in'_'m]
I=9**9
dp=[I]*2**n
dp[0]=0
for i,d in enumerate(dp):
    if d==I:continue
    for a,c in e:
        b,x=i,d+a
        for j in c:b|=j
        if dp[b]>x:dp[b]=x
print(-(dp[-1]==I)or dp[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
e=[(int(input().split()[0]),list(map(int,input().split())))for _ in range(m)]
INF=10**18
dp=[INF]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]>=INF:continue
    for a,c in e:
        bit=i
        for j in c:
            bit|=2**(n-j)
        dp[bit]=min(dp[bit],dp[i]+a)
a=dp[-1]
if a>=INF:
    print(-1)
else:
    print(dp[-1])