Harryxun/stf_run huggingface dataset:
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def remove_Edge(N,Ef,Eb,start,goal):
    v = connect_dfs(N,Ef,start) & connect_dfs(N,Eb,goal)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            E[j].pop(i)

def Bellman_Ford(N,E,start,INFTY=10**18):
    def update(dist,N,E,start):
        done = [False]*N
        done[start] = True
        q = [start]
        d = dist[:]
        while q:
            i = q.pop()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    q.append(j)
                    done[j] = True
        return d
    #
    d = [INFTY]*N
    d[start] = 0
    for _ in range(N-1):
        d = update(d,N,E,start)
    if d!=update(d,N,E,start):
        return None
    else:
        return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]
    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    
    remove_Edge(N,E,Eb,0,N-1)
    d = Bellman_Ford(N,E,0)
    if d == None:
        print("inf")
    else:
        print(-d[-1])
    
main()

### FIXED CODE ###

N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c


INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True

for _ in range(N-1):update()
dc = d[:]
for _ in range(N):update()
if dc[-1]!=d[-1]:
    print("inf")
else:
    print(-d[-1])
import numpy as np
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_mat = np.array(A)
B_mat = np.array(B)
C_mat = B_mat - A_mat
C = C_mat.tolist()
x = 10 ** 10
num = 0
for i in range(len(C)):
    if 0 <= C[i] < x:
        x = C[i]
        num = i
if x == 10 ** 10:
    print('No')
else:
    A.pop(num)
    B.pop(num)

    A.sort()
    B.sort()

    A1_mat = np.array(A)
    B1_mat = np.array(B)

    C1_mat = B1_mat - A1_mat
    if np.all(C1_mat >= 0):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n = int(input())
if n % 2 == 1:
    ans = (n-1) // 2
else:
    ans = (n-2) // 2
print(ans)
import itertools
X=int(input())
li=[i**5 for i in range(128)]#
for v in itertools.permutations(li, 2):
    v=list(v)
    v.sort()
    if v[1]-v[0]==X:#両方プラスの時
        A=v[0]**0.2
        B=v[1]**0.2
        print(str(int(A))+" "+str(int(B)))
        break
    elif v[0]+v[1]==X:#v[1]がマイナスの時
        A=v[0]**0.2
        B=-1*((v[1])**0.2)
        print(str(int(A))+" "+str(int(B)))
        break
#ans=(i-j)*(i**4+(i**3)*j+(i**2)*(j**2)+i*(j**3)+j**4)
#(ａ－ｂ)(ａ⁴＋ａ³ｂ＋ａ²ｂ²＋ａｂ³＋小さい

### FIXED CODE ###

S=input()
if S=="ABC":
    print("ARC")
else:
    print("ABC")
N=number=int(input())
X_list=list(map(int, input().split()))

if N==1:
    print("0")
else:
    X_min=min(X_list)
    X_max=max(X_list)
    for i in range(X_min,X_max):
        sum_pow=0
        for j in range(N):
            sum_pow+=(X_list[j]-i)**2
        if i==X_min:
            min_pow=sum_pow
        if min_pow>sum_pow:
            min_pow=sum_pow
    print(min_pow)

### FIXED CODE ###

N=number=int(input())
X_list=list(map(int, input().split()))
min_pow=0
if N==1:
    print("0")
else:
    X_min=min(X_list)
    X_max=max(X_list)
    for i in range(X_min,X_max):
        sum_pow=0
        for j in range(N):
            sum_pow+=(X_list[j]-i)**2
        if i==X_min:
            min_pow=sum_pow
        if min_pow>sum_pow:
            min_pow=sum_pow
    print(min_pow)
N, blue, red = map(int, input().split())


def count_blue(N, blue, red):
  
  if blue == 0:
    return 0
  elif N <= blue:
    return N
  elif N <= blue + red:
    return blue
  else:
    return (N // (blue + red) * blue) + count_blue(N // (blue + red), blue, red)
  
  
print(count_blue(N, blue, red))

### FIXED CODE ###

N, blue, red = map(int, input().split())

ans = N // (blue + red) * blue
rem = N % (blue + red)
ans += min(rem, blue)
print(ans)
P=[1,10,9,12,3,4]
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%(10**9+7)
    return B
S=reversed(input())
A=[0]
p=0
for s in S
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
    p=(p+1)%6
print(A[5])


### FIXED CODE ###

P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])
a,b = [int(input()),int(input())]

if a*b%2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[K-1])

### FIXED CODE ###

A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K])
def solve(s, a, b):
    if a == 1:
        return s + b * 2 - 1
    if b == 1:
        return s + a * 2 - 1
    if a == b:
        return s + a
    elif a > b:
        return solve(s + b * 2, a - b, b)
    else:
        return solve(s + a * 2, a, b - a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

### FIXED CODE ###

def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
ans = 0
for i in range(n):
    if((i - k) < 0):
        if(t[i] == 'r'):ans += p
        elif(t[i] == 's'):ans += r
        else:ans += s
        continue
    
    else:
        if(t[i-k] == t[i]):t = t[:i] + 'n' + t[i+1:]
        else:
            if(t[i] == 'r'):ans += p
            elif(t[i] == 's'):ans += r 
            else:ans += s
print(score)


### FIXED CODE ###

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
ans = 0
for i in range(n):
    if ((i - k) < 0):
        if (t[i] == 'r'):
            ans += p
        elif (t[i] == 's'):
            ans += r
        else:
            ans += s
        continue

    else:
        if (t[i - k] == t[i]):
            t = t[:i] + 'n' + t[i + 1:]
        else:
            if (t[i] == 'r'):
                ans += p
            elif (t[i] == 's'):
                ans += r
            else:
                ans += s
print(ans)
import math
a = [int(input()).split() for l in range(2)]
if sum(a[1]) >= a[0][0]
	print("Yes")
else
	print("No")

### FIXED CODE ###

a = [list(map(int,input().split())) for l in range(2)]

if sum(a[1]) >= a[0][0]:
    print("Yes")
else:
    print("No")
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
if N == 3:
    print(1, 2, 3)

last = set(range(1, N + 1))
result = {}


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        result[self.v] = last.pop()
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
root = nodes[1]
root.set_rank(None, 0)
print(' '.join(str(result[i]) for i in range(1, N + 1)))

exit()

# ---
group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
indexes = [0] * 3
result = {}
for node in group[0]:
    indexes[0] += 1
    result[node.v] = indexes[0] * 3
    last.remove(indexes[0] * 3)
for node in group[1]:
    if indexes[1] >= N // 3 + ((N % 3) >= 1):
        indexes[0] += 1
        result[node.v] = indexes[0] * 3
        last.remove(indexes[0] * 3)
    else:
        result[node.v] = indexes[1] * 3 + 1
        last.remove(indexes[1] * 3 + 1)
        indexes[1] += 1
for node in group[2]:
    result[node.v] = last.pop()
#
#     result[node.v] = indexes[2] * 3 + 2
#     indexes[2] += 1


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))
A1, A2, A3 = map(int, input().split())
print(min(abs(A1 - A2) + abs(A2 - A3), abs(A1 - A3) + abs(A2 - A3), abs(A2 - A1) + abs(A1 - A3), abs(A2 - A3) + abs(A3 - A1), abs(A3 - A1) + abs(A1 - A2), abs(A3 - A2) + abs(A2 - A1))

### FIXED CODE ###

A1, A2, A3 = map(int, input().split())
print(min(abs(A1 - A2) + abs(A2 - A3), abs(A1 - A3) + abs(A2 - A3), abs(A2 - A1) + abs(A1 - A3), abs(A2 - A3) + abs(A3 - A1), abs(A3 - A1) + abs(A1 - A2), abs(A3 - A2) + abs(A2 - A1))
     )
import math

s = input()
i = int(input())

isR = False
for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                s = s + q[2]
            else:
                s = q[2] + s
        else:
            if q[1] == "1":
                s = q[2] + s
            else:
                s = s + q[2]

if isR:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

import math

s = input()
i = int(input())

isR = False
head = []
tail = []

for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                tail.append(q[2])
            else:
                head.append(q[2])
        else:
            if q[1] == "1":
                head.append(q[2])
            else:
                tail.append(q[2])

ans = "".join(head[::-1]) + s + "".join(tail)

if isR:
    print(ans[::-1])
else:
    print(ans)
N = int(input())
S = [input() for _ in range(N)]
check_box = []
ans = 0
for s in S:
  s = sorted(s)
  s = ''.join(s)
  print(s)
  print(check_box)
  if s in check_box:
    ans += 1
  else:
    check_box.append(s)
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
S = [str(sorted(input())) for _ in range(N)]
count = 0
for i in Counter(S).values():
  count += i*(i-1)//2
print(count)
import sympy

N=int(input())
l=[]
for i in sympy.divisors(N):
    l.append([i,N/i])
L=len(l)
s=[0]*L
for j in range(L):
    s[j]=l[j][0]+l[j][1]
print(int(min(s))-2)

### FIXED CODE ###

N=int(input())
l=[]
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        l.append([i,N/i])
L=len(l)
s=[0]*L
for j in range(L):
    s[j]=l[j][0]+l[j][1]
print(int(min(s))-2)
s = str(input())
K = int(input())

def find(str):
	lt = []
	for start in range(len(str)):
		for end in range(start + 1, len(str) + 1):
			lt.append(str[start:end])
	lt = list(set(lt))
	lt.sort()

	return lt

s_pt = list(set(list(s)))
s_pt.sort()
ans = []

for i in range(5):
	ind = [ix for ix, x in enumerate(s) if x == s_pt[i]]
	for j in ind:
		ans += find(s[j:min(j+5, len(s))])
	if len(ans) >= 5:
		break
ans = list(set(ans))
ans.sort()
print(ans[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())

def find(str):
	lt = []
	for start in range(len(str)):
		for end in range(start + 1, len(str) + 1):
			lt.append(str[start:end])
	lt = list(set(lt))
	lt.sort()

	return lt

s_pt = list(set(list(s)))
s_pt.sort()
ans = []
for i in range(min(5, len(s_pt))):
	ind = [ix for ix, x in enumerate(s) if x == s_pt[i]]
	for j in ind:
		ans += find(s[j:min(j+5, len(s))])
	ans = list(set(ans))
	if len(ans) >= 5:
		break
ans = list(set(ans))
ans.sort()
print(ans[K-1])
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[0 if si == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()
N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    j = i
    for j in range(sorted, i, -1):
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        sorted = j
        break
  if (i + 1) == j:
    break
print(str(ans))

### FIXED CODE ###

N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    for j in range(sorted, i, -1):
      sorted = j - 1
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        break
  if (i + 1) > sorted:
    break
print(str(ans))
n1,n2=int(n[:2]),int(n[2:])
if (n1>12 and n2>12) or (n1==0 and n2==0):
    print("NA")
elif (n1!=0 and n1<=12) and (n2!=0 and n2<=12):
    print("AMBIGUOUS")
elif n1!=0 and n1<=12:
    print("MMYY")
elif n2!=0 and n2<=12:
    print("YYMM")
else:
    print("errer")



### FIXED CODE ###

n=input()

n1,n2=int(n[:2]),int(n[2:])
if (n1>12 and n2>12) or (n1==0 and n2==0):
    print("NA")
elif (n1!=0 and n1<=12) and (n2!=0 and n2<=12):
    print("AMBIGUOUS")
elif n1!=0 and n1<=12:
    print("MMYY")
elif n2!=0 and n2<=12:
    print("YYMM")
else:
    print("NA")
r,g,b,n = map(int,input().split())
lis=[r,g,b]
lis.sort()
cnt=0
for i in range(n//lis[2] + 1):
  for l in range(n//lis[1]+1):
    for m in range(n//lis[0]+1):
      if i*lis[2]+l*lis[1]+i*lis[0] = n:
        cnt+=1
print(cnt)

### FIXED CODE ###

b,r,g,n=map(int,input().split())
ans=0
for i in range(3000//r+1):
    for j in range(3000//g+1):
        if n-j*g-i*r>=0 and (n-j*g-i*r)%b==0:
            ans+=1
print(ans)
from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.r = [-1 for i in range(num)]
    def root(self,x:int):
        if(self.r[x] < 0):
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return False
        if(self.r[rx] > self.r[ry]):
            rx,ry = ry,rx
        self.r[rx] += self.r[ry]
        self.r[ry] = rx
        return True
    def size(self,x:int):
        return -self.r[self.root(x)]

N,M = map(int,input().split())
group = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
ans = 0
for i in range(N):
    ans = max(ans,group.size(i))
print(group.r)
print(ans)


### FIXED CODE ###

D,T,S = map(int,input().split())
if(D>T*S):
    print("No")
else:
    print("Yes")
import sys
n = int(sys.stdin.radline())
li = list(map(int, sys.stdin.readline().split()))
s = 0
i = 0
while i < n-1:
  s += li[i] * li[i+1]
  i += 1
print(s)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
s = 0
i = 0
while i < n-1:
  k = i+1
  while k < n:
    s += li[i] * li[k]
    k += 1
  i += 1
print(s)
N = int(input())
A = [int(input()) for i in range(N)]


def solve(A):
    if len(A) == 0:
        return
    indexList = []
    last = A[0]
    for i, v in enumerate(A):
        if v > last:
            indexList.append(i)
            last = v
    del A[0]
    for i in indexList:
        del A[i-1]


counter = 0
while len(A) > 0:
    solve(A)
    counter += 1

print(counter)

### FIXED CODE ###

import bisect
N = int(input())
A = [-int(input()) for i in range(N)]


dp = []
for a in A:
    i = bisect.bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(len(dp))
# -*- coding: utf-8 -*-
n = str(input())
m.replace(1,9:9,1)

### FIXED CODE ###

# -*- coding utf-8 -*-
n = str(input())
S = n.replace("1","8")
T = S.replace("9","1")
U = T.replace("8","9")
print(U)
s=[input() for _ in range(int(input()))]
t=[input() for _ in range(int(input()))]
l=list(set(n))
#s内の重複消去　リストに変更
print(max(0,max(s.count(l[i])-t.count(l[i]) for i in range(len(l)))))

### FIXED CODE ###

N=int(input())
s=[input() for _ in range(N)]
M=int(input())
t=[input() for _ in range(M)]
def ans1(x):
    return s.count(x)-t.count(x)
ans2=0
ans_1=0
for S in s:
    if ans1(S)>0 and ans1(S)>ans2:
            ans2=ans1(S)
if ans2>=0:
    print(ans2)
else:
    print("0")
/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
import sys

n = sys.stdin.readline().rstrip()

sum = 0
for i in range(n):
  line = sys.stdinp.readline().rstrip().split(" ")
  if(line[1] == "BTC"):
    sum += float(line[0]) * 380000.0
  else:
    sum += float(line[0])
print(sum)

### FIXED CODE ###

import sys

n = int(sys.stdin.readline().rstrip())

sum = 0
for i in range(n):
  line = sys.stdin.readline().rstrip().split(" ")
  if(line[1] == "BTC"):
    sum += float(line[0]) * 380000.0
  else:
    sum += float(line[0])
print(sum)
import collections
N, M = map(int, input().split())
H = list(map(int, input().split()))

root = dict()

for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] >= H[B-1]:
        root[A-1] = H[A-1]
        if B-1 in root.keys():
            root.pop(root[B-1])
    else:
        root[B - 1] = H[B - 1]
        if A-1 in root.keys():
            root.pop(root[A-1])


print(len(root))


### FIXED CODE ###

import copy
N, M = map(int, input().split())
H = list(map(int, input().split()))

H2 = copy.copy(H)
for i in range(M):
    A, B = map(int, input().split())
    if H[A - 1] > H[B - 1]:
        H2[B - 1] = False
    elif H[A - 1] < H[B - 1]:
        H2[A-1] = False
    else:
        H2[A - 1] = False
        H2[B - 1] = False

H3 = H2.count(False)

print(len(H) - H3)
# -*- coding: utf-8 -*-
from math import factorial

N, M = map(int, input().split())
a = [int(input()) for x in range(M)]

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp += factorial(n) / factorial(i) / factorial(n - i)

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import factorial

N, M = map(int, input().split())
a = [int(input()) for x in range(M)]

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))
N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
   ans *= A[i]
   if ans > 10**18:
     ans = -1
     break

 print(ans) 


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
 
if 0 in a: 
    ans = 0
else:
    ans = 1
    for ai in a:
        ans *= ai
        if ans > 10**18:
            ans = -1
            break
print(ans)
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = np.zeros(N)
for a in A:
    ans[a-1] += 1
for o in ans:
    print(int(o))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = np.zeros(N)
for a in A:
    ans[a-1] += 1
for o in ans:
    print(int(o))
S = input()
T = input()
k = len(T)
m = 0
for i in range(k):
  if S[i] != T[i]:
    m += 1
print(m)


### FIXED CODE ###

a = int(input())
k = a + a**2 + a**3
print(k)
print(2 * r *3.14159265359 )

### FIXED CODE ###

print(2 * int(input()) *3.14159265359 )