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

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
p = 0
q = 0
for i in range(N):
  if p + A[i] > K:
    break
  a.append(p+A[i])
  p += A[i]
for i in range(M):
  if q + B[i] > K:
    break
  b.append(q+B[i])
  q += B[i]
ans = 0
for n, s in enumerate(a):
  if s > K:
    break
  for m, t in enumerate(b):
    if s + t <= K:
      ans = max(ans, n+m)
    else:
      break
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
p = 0
for i in range(N):
  p += A[i]
  a.append(p)
q = 0
for j in range(M):
  q += B[j]
  b.append(q)
ans = 0
j = M
for i in range(N+1):
  if a[i] > K:
    break
  while a[i] + b[j] > K:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1 or p == 0:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

def f(x):
    ans = 0
    if x == 0:
        return ans
    for i in range(31):
        if ((x>>i)&1) == 1:
            ans += 1
    return f(x%ans) + 1

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        if cnt-1 !=  0:
            t = f((r2-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
        else:
            t = 0
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    print(i)




### FIXED CODE ###

def cin():
    return input().split()
def qpow(a,b,p):
    if p == 1 or p == 0:
        return 0
    a = (a%p+p)%p
    ans = 1
    while b!=0:
        if (b&1) != 0:
            ans = (ans * a) % p
        b >>= 1
        a = a * a  % p
    return ans

def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1

n = int(input())
x = list(input())
x = x[::-1]
cnt = 0;l = len(x)
r1 = 0;r2 = 0
for i in x:
    if i == '1':
        cnt += 1
i = 0
while i < l:
    if x[i] == '1':
        r1 += qpow(2,i,cnt+1)
        r2 += qpow(2,i,cnt-1)
    i += 1
i = 0
a = []
while i < l:
    if x[i] == '0':
        t = f((r1+qpow(2,i,cnt+1))%(cnt+1))+ 1
    else:
        if cnt-1 !=  0:
            t = f((r2-qpow(2,i,cnt-1)+(cnt-1))%(cnt-1)) + 1
        else:
            t = 0
    i += 1
    a.append(t)
a = a[::-1]
for i in a:
    print(i)
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for i, l in enumerate(L):
        re += i - getsum(l)
        addbit(l)
    return re
def calc(Z):
    Z.sort()
    l, r = -1<<31, 1<<31
    for i in range(63):
        m = (l+r) / 2
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        if bit(A) > N*(N-1)//4:
            l = m
        else:
            r = m
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p

print(ans)

### FIXED CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

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

# -*- coding: utf-8 -*-
K, S = map(int, input().split())

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            s = x + y + z
            if s == S:
                count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K, S = map(int, input().split())

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1

print(count)
### BUGGY CODE ###

def dist(ai:int, bi:int, aj:int, bj:int):
    return abs(ai-aj)+abs(bi-bj)

h, w, d = map(int, input().split())
p = {}
for i in range(h):
    tmpstr = input().split()
    for j in range(w):
        tmpchar = int(tmpstr[j])
        p[tmpchar] = (i, j)

q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    curnum = l
    t = (r-l)//d
    for _ in range(t):
        curl, curr = p[curnum]
        nextl, nextr = p[curnum+d]
        ans += dist(curl, curr, nextl, nextr)
        curnum += d
    print(ans)


### FIXED CODE ###

def dist(ai:int, bi:int, aj:int, bj:int):
    return abs(ai-aj)+abs(bi-bj)

h, w, d = map(int, input().split())
p = {}
for i in range(h):
    tmpstr = input().split()
    for j in range(w):
        tmpchar = int(tmpstr[j])
        p[tmpchar] = (i, j)
dsum = [0]*d
for i in range(d, h*w):
    curl, curr = p[i+1]
    prel, prer = p[i-d+1]
    diff = dist(curl, curr, prel, prer)
    tmpd = dsum[i-d]+diff
    dsum.append(tmpd)

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(dsum[r-1]-dsum[l-1])
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in fl:
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = []
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	x = 0
	for L in range(N-1):
		first = P[L]
		second = 0
		for i in range(1,N-L):
			ind = L+i
			if P[ind]>first:
				second = first
				first = P[ind]
			elif P[ind]>second:
				second = P[ind]

			x = x+second

	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

	N = int(input().strip())
	P = list(map(int,input().strip().split()))

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

n=int(input())
p=input().split()
num=0
for i in range(n):
    for j in range(i+1):
        if int(p[j])<int(p[i]):
            break
        if j==i:
            num+=1
print(num)


### FIXED CODE ###

n=int(input())
p=input().split()
num=0
mini=int(p[0])
for i in range(n):
    if int(p[i])<=mini:
        num+=1
        mini=int(p[i])
print(num)
### BUGGY CODE ###

from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [list(input()) for _ in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))



### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

N = int(input())
S = input()

left = 0
right = 1
max_length = 0

while left < N:
    serch_str = S[left:right]
    left_str = S[right:]
    if serch_str in left_str:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
        right = left + 1

print(max_length)


### FIXED CODE ###

N = int(input())
S = input()

left = 0
right = 1
max_length = 0

while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1

print(max_length)
### BUGGY CODE ###

def brute(i,m):
    if m == 0:
        return True
    elif i >= n or m < 0:
        return False
    return brute(i+1,m) | brute(i+1,m-n_list[i])

n = int(input())
n_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))

for num in q_list:
    print('yes') if brute(0,num) else print('no')



### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))
bits = 1

for a in a_list:
    bits |= bits << a

for q in q_list:
    if (bits>>q)&1:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    n0=0
    print(n0)
    s=input()
    if s=="Vacant":sys.exit()
    left,right=0,n
    mid=(right+left)//2
    sl=s
    print(mid)
    sm=input()
    while sm!="Vacant" and right>left:
        if ((mid-left)%2==0 and sm==sl) or ((mid-left)%2==1 and sm!=sl):
            left=mid
            sl=sm
        else:
            right=mid
        mid=(right+left)//2
        print(mid)
        sm=input()        


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x
### BUGGY CODE ###

n = int(input())
num_list = list(map(int, input().split()))
b = []
for a in num_list:
    b.append(a)
    b = [i for i in (reversed(b))]
for i in range(len(b)):
    if i != len(b)-1:
        print(b[i],end="")
        print(" ", end="")
    else:
        print(b[i])
    

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
a1_list = []
a2_list = []
n_list = [0]*n
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            a1_list.append(a_list[i])
        else:
            a2_list.append(a_list[i])
    for i in reversed(a2_list):
        print(i, end="")
        print(" ", end="")
    for i in a1_list:
        if i != a1_list[int((n-2)/2)]:
            print(i, end="")
            print(" ", end="")
        else:
            print(i)
else:
    for i in range(1,n):
        if i % 2 == 0:
            a1_list.append(a_list[i])
        else:
            a2_list.append(a_list[i])
    for i in reversed(a1_list):
        print(i, end="")
        print(" ", end="")
    print(a_list[0], end="")
    print(" ", end="")
    for i in a2_list:
        if i != a2_list[int((n-2)/2)]:
            print(i, end="")
            print(" ", end="")
        else:
            print(i)
### BUGGY CODE ###

x,n=map(int,input().split())
if n==0:
    print(x)
else:
    p=list(map(int,input().split()))
    a=0
    d=0
    while a==0:
        if x-d in p:
            if x+d in p:
                d+=1
            else:
                a=x+d
        else:
            a=x-d
    print(a)

### FIXED CODE ###

import sys
input=sys.stdin.readline
x,n=map(int,input().split())
if n==0:
    print(x)
else:
    p=list(map(int,input().split()))
    d=0
    while True:
        if x-d in p:
            if x+d in p:
                d+=1
            else:
                a=x+d
                break
        else:
            a=x-d
            break
    print(a)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
n = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
for k in range(A):
  for m in range(B):
    n.append(int(a[k])+int(b[m]))
print(min(min(l), min(n)))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(input().split())
b = list(input().split())
l = []
for i in range(M):
  x, y, c = map(int, input().split())
  l.append(int(a[x-1])+int(b[y-1])-c)
l.sort()
n = int(min(a)) + int(min(b))
print(min(l[0], n))
### BUGGY CODE ###

import numpy as np
import time
import random
import sys
input=sys.stdin.readline
#N=100000
N=int(input())
D=np.array(list(map(int,input().split())))
#D=np.concatenate([np.array([0]),np.array([random.randint(1,1000) for _ in range(99999)])])

#print(np.count_nonzero(D==0))
if D[0]!=0 or np.count_nonzero(D==0)!=1:
    print(0)
    exit()

k=max(D)


ans=1
past=1
for i in range(1,k+1):
    n=np.count_nonzero(D==i)
    if n==0:
        print(0)
        #ptime=time.time()-start
        #print(ptime)
        exit()
    ans*=past**n
    ans%=998244353
    past=n

print(ans)
#ptime=time.time()-start
#print(ptime)

### FIXED CODE ###

import collections
 
N=int(input())
D=list(map(int,input().split()))
 
c=collections.Counter(D)
 
max_D=max(D)
ans=1
previous_leaf=1
 
if D[0]!=0:
    ans=0
elif c[0]!=1:
    ans=0
else:
    for i in range(1,max_D+1):
        ans*=(previous_leaf**c[i])
        ans%=998244353
        previous_leaf=c[i]
 
print(ans)
### BUGGY CODE ###

from collections import defaultdict

INF = 10 ** 10
def main():
    N, M = map(int, input().split())

    dp = [[INF] * N for _ in range(N)]
    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c
        edges.append((a, b, c))
        
    for i in range(N):
        dp[i][i] = 0

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = 0
    for a, b, c in edges:
        found = False
        for s in range(N):
            for e in range(N):
                if dp[s][a] + c + dp[b][e] == dp[s][e]:
                    found = True
                    break
            if found:
                break
        if not found:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict

INF = 10 ** 10
def main():
    N, M = map(int, input().split())

    dp = [[INF] * N for _ in range(N)]
    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        dp[a][b] = c
        dp[b][a] = c
        edges.append((a, b, c))

    for i in range(N):
        dp[i][i] = 0

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = 0
    for a, b, c in edges:
        for s in range(N):
            if dp[s][a] + c == dp[s][b]:
                break
        else:
            ans += 1
    print(ans)


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

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for a in A:
    ans += l // a

print(ans % (10**9 + 7))

### FIXED CODE ###

import fractions
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
N = int(input())
A = list(map(int, input().split()))
 
l = 1
for a in A:
    l = lcm(l, a)
 
ans = 0
for a in A:
    ans += l // a
 
print(ans % (10**9 + 7))
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [0]*(W+1)

for w,v in wvs:
    for i in reversed(range(W+1)):
        dp[i] = max(dp[i-w] + v,dp[i])
        if i == w:
            break

print(max(dp))


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [0]*(W+1)

for w,v in wvs:
    for i in reversed(range(W+1)):
        dp[i] = max(dp[i-w] + v,dp[i])
        if i == w:
            break

print(max(dp))