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

import itertools
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く

for judge in judge_list:
    score = 0
    num = 0
    flag = 0
    for i in range(1, len(judge) + 1):
        if score >= G:
            break
        
        if judge[-i] == 1:
            pass
        
        if judge[-i] == 2:
            score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
            num += P[-i][0]
            
        if (judge[-i] == 0) and (flag == 0):
            for j in range(P[-i][0]):
                if score >= G:
                    break
                score += 100 * (D - i + 1)
                num += 1
            flag = 1
                        
    if score >= G:
        min_num = min(num, min_num)

print(min_num)           

### FIXED CODE ###

import itertools
from collections import Counter
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く


for judge in judge_list:
    score = 0
    num = 0
    d = Counter() #インスタンスを生成
    d.update(judge)
    if (d[0] <= 1):
        for i in range(1, len(judge) + 1):
            if score >= G:
                break

            if judge[-i] == 1:
                pass

            if judge[-i] == 2:
                score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
                num += P[-i][0]

            if (judge[-i] == 0):
                for j in range(P[-i][0]):
                    if score >= G:
                        break
                    score += 100 * (D - i + 1)
                    num += 1
                        
        if score >= G:
            min_num = min(num, min_num)

print(min_num)
### BUGGY CODE ###

n, k = map(int, input().split())
aas = list(map(int, input().split()))
scores = []
cnt = 0
tmp = 1
for i in range(n):
    tmp *= aas[i]
    if i >= k-1:
        scores.append(tmp)
        tmp //= aas[i-(k-1)]
for i in range(1,len(scores)):
    if scores[i] > scores[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k = map(int, input().split())
aas = list(map(int, input().split()))
scores = []
for i in range(k,n):
    if aas[i] > aas[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

c = []
for i in range(3):
    x, y, z = map(int, input().split())
    c.append(x)
    c.append(y)
    c.append(z)

max_c = max(c) + 1

for i in range(max_c):
    for j in range(max_c):
        for k in range(max_c):
            for l in range(max_c):
                for m in range(max_c):
                    for n in range(max_c):
                        if c[0] == i + l and c[1] == i + m and c[2] == i + n and c[3] == j + l and c[4] == j + m and c[5] == j + n and c[6] == k + l and c[7] == k + m and c[8] == k + n:
                            print('Yes')
                            exit()
print('No')


### FIXED CODE ###

c = []
for i in range(3):
    x, y, z = map(int, input().split())
    c.append(x)
    c.append(y)
    c.append(z)

for a1 in range(101):
    for a2 in range(101):
        for a3 in range(101):
            b1 = c[0] - a1
            b2 = c[1] - a1
            b3 = c[2] - a1
            if c[3] == a2 + b1 and c[4] == a2 + b2 and c[5] == a2 + b3 and c[6] == a3 + b1 and c[7] == a3 + b2 and c[8] == a3 + b3:
                print('Yes')
                exit()
print('No')
### BUGGY CODE ###

h,n=map(int,input().split())
MAX_NUM=9999999999
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
dp=[MAX_NUM for _ in range(h+1)]
dp[0]=0

for i in range(h):
    if(dp[i]!=MAX_NUM):
        for j in range(n):
            a,b=ab[j]
            ind = i+a if i+a<h else -1
            dp[ind]=min(dp[ind],dp[i]+b)
print(dp[-1])



### FIXED CODE ###

h,n=map(int,input().split())
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
max_a=max([a for a,b in ab])
dp=[0 for _ in range(h+max_a)]

for i in range(1,len(dp)):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))


#
# MAX_NUM=9999999999
# ab=[]
# for _ in range(n):
#     ab.append(list(map(int,input().split())))
# dp=[MAX_NUM for _ in range(h+1)]
# dp[0]=0
#
# for i in range(h):
#     if(dp[i]!=MAX_NUM):
#         for j in range(n):
#             a,b=ab[j]
#             ind = i+a if i+a<h else -1
#             dp[ind]=min(dp[ind],dp[i]+b)
# print(dp[-1])
### BUGGY CODE ###

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

a = [0] * n
for i in range(n):
    a[d[i]] += 1

if a[0] == 1 and d[0] == 0:
    ans = 1
    for i in range(1, n):
        ans *= a[i-1]**a[i]

    print(ans % 998244353)
else:
    print(0)

### FIXED CODE ###

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

a = [0] * n
for i in range(n):
    a[d[i]] += 1

if a[0] == 1 and d[0] == 0:
    ans = 1
    for i in range(1, n):
        ans *= a[i-1]**a[i]
        ans %= 998244353

    print(ans)
else:
    print(0)
### BUGGY CODE ###


num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

# dpの初期化
dp = [[0 for _ in range(num + 1)] for _ in range(weight_limit + 1)]

for w in range(1, weight_limit + 1):
    for n in range(1, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if weight <= w:
            dp[w][n] = max(value + dp[w - weight][n-1], dp[w][n-1])

        else:
            dp[w][n] = dp[w][n-1]

print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = np.zeros(weight_limit + 1)

for n in range(num):
    w = wv_list[n][0]
    v = wv_list[n][1]
    dp[w:] = np.maximum(dp[:-w] + v, dp[w:])

print(int(dp[-1]))
### BUGGY CODE ###

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

def nax(a, b):
    if a == '-':
        return b
    return a if int(a)>int(b) else b


match = [2,5,5,4,5,6,3,7,6]
# dp[i]  : iほんのマッチを使ってできる数値の最大値
dp = ['-'] * 10101
dp[0] = ''

for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+match[a-1]] = nax(dp[i+match[a-1]], dp[i] + chr(ord('0') + a))

print(dp[N])

### FIXED CODE ###

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

def nax(a, b):
    if a == '-':
        return b
    if len(a) != len(b):
        return a if len(a)>len(b) else b
    return a if a>b else b


match = [2,5,5,4,5,6,3,7,6]
# dp[i]  : iほんのマッチを使ってできる数値の最大値
dp = ['-'] * 11000
dp[0] = ''

for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+match[a-1]] = nax(dp[i+match[a-1]], dp[i] + chr(ord('0') + a))

print(dp[N])
### BUGGY CODE ###

n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(abs(int(l[i][0])-a)//k)%2
           h=(abs(int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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




def main():
    data = list(input())
    # dp = [[0 for i in range(4)] for i in range(len(data) + 1)]
    # dp[len(data)][3] += 1

    dp = [0, 0, 0, 1]

    dic = {0:'A', 1:'B', 2:'C'}
    for i in range(len(data))[::-1]:
        element = data[i]
        for j in range(4):
            if j == 3:
                if element == '?':
                    dp[j] *= 3
            else:
                if dic[j] == element:
                    dp[j] += dp[j + 1]

                elif element == '?':
                    dp[j] = dp[j] * 3 + dp[j + 1]


    mod = 10 ** 9 + 7
    print(dp[0] % mod)





if __name__ == '__main__':
    main()


### FIXED CODE ###




def main():
    data = list(input())
    # dp = [[0 for i in range(4)] for i in range(len(data) + 1)]
    # dp[len(data)][3] += 1

    dp = [0, 0, 0, 1]
    mod = 10 ** 9 + 7

    dic = {0:'A', 1:'B', 2:'C'}
    for i in range(len(data))[::-1]:
        element = data[i]
        for j in range(4):
            if j == 3:
                if element == '?':
                    dp[j] *= 3
            else:
                if dic[j] == element:
                    dp[j] += dp[j + 1]

                elif element == '?':
                    dp[j] = dp[j] * 3 + dp[j + 1]

            dp[j] %= mod



    print(dp[0] % mod)





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

N,M=[int(i) for i in input().split()]
PY=[[] for _ in range(N)]
py=[]

for i in range(M):
    p,y=[int(i) for i in input().split()]
    p-=1
    py.append((p,y))
    PY[p].append(y)
    PY[p]=sorted(PY[p])

for i in range(M):
    p,y=py.pop(0)
    p_zero=6-len(str(p))
    y_zero=6-len(str(PY[p].index(y)))
    print("0"*p_zero + str(p+1) + "0"*y_zero + str(PY[p].index(y)+1))


### FIXED CODE ###

N,M=[int(i) for i in input().split()]
PY=[[] for _ in range(N)]
py=[]

for i in range(M):
    p,y=[int(i) for i in input().split()]
    PY[p-1].append((y,i))

ans=[None]*M
for j,py in enumerate(PY): #jが県番号
    py.sort()
    for k,(y,i) in enumerate(py):
        ans[i]=str(j+1).zfill(6) + str(k+1).zfill(6)

print(*ans,sep="\n")
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
t = [0]*2 + list(map(int, input().split())) + [0]
v = [0] + list(map(int, input().split())) + [0]
N += 3

at = list(accumulate(t))
T = at[-1]

s = [0]*(2*T+1)

minvs = []
for i in range(2*T+1):
    t = i*0.5
    minv = 10**10
    for j in range(N-1):
        if t < at[j]:
            tmpv = v[j] + (at[j]-t)
        elif at[j] <= t and t <= at[j+1]:
            tmpv = v[j]
        else:
            tmpv = v[j] + (t-at[j+1])
        minv = min(minv, tmpv)
    minvs.append(minv)
ans = 0.0
for i in range(2*T):
    ans += (minvs[i]+minvs[i+1])*0.25
print(ans)


### FIXED CODE ###

from itertools import accumulate
N = int(input())
t = [0]*2 + list(map(int, input().split())) + [0]
v = [0] + list(map(int, input().split())) + [0]
N += 3

at = list(accumulate(t))
T = at[-1]

s = [0]*(2*T+1)

minvs = []
for i in range(2*T+1):
    t = i*0.5
    minv = 10**10
    for j in range(N-1):
        if t < at[j]:
            tmpv = v[j] + (at[j]-t)
        elif at[j] <= t and t <= at[j+1]:
            tmpv = v[j]
        else:
            tmpv = v[j] + (t-at[j+1])
        minv = min(minv, tmpv)
    minvs.append(minv)
ans = 0.0
for i in range(2*T):
    ans += (minvs[i]+minvs[i+1])*0.25
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    k=K//i
    GCD[i]=(k**N)%mod

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)

### FIXED CODE ###

N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    GCD[i]=pow(K//i,N,mod)

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)
### BUGGY CODE ###

import sys
def main():
   input = sys.stdin.buffer.readline
   n,m = map(int, input().split())
   results = {}
   p_list=[]
   y_list=[]
   cnt = 0
   for i in range(m):
       p,y = map(int, input().split())
       p_list.append(p)
       y_list.append(y)
       if results.get(p) is None:
           results[p] = [y]
       else:
           results[p].append(y)
   for i ,p in enumerate(p_list):
       p_sort = sorted(results[p])
       import bisect
       print('{:006}'.format(p)+'{:006}'.format(bisect.bisect_left(p_sort,y_list[i])+1))
if __name__ == "__main__":
    main()

### FIXED CODE ###

N, M = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]

convertedPY = [
    {'index': i,
     'city': py[0],
     'year': py[1]
     } for i, py in enumerate(PY)
]
'''
3 4
1 32
3 64
3 63
1 33

'''
convertedPY = sorted(convertedPY, key=lambda a: (a['city'], a['year']))
answer = []
cnt = 0
tmp = convertedPY[0]['city']
#print(convertedPY)
result = []
for py in convertedPY:
    #print(tmp)
    temp_dict = {}
    if tmp == py['city']:
        cnt += 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
    else:
        cnt = 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
        tmp = py['city']


result = sorted(result, key=lambda a: a['index'])
#print(result)
for r in result:
    print(r['answer'])

'''
3
21 -11
81234 52141 94124
'''

#print(PY)
### BUGGY CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,x,y = imap()
ans = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        ans.append(min(a,b,c))
    
cnt = col.Counter(ans)
for i in range(1,n): print(cnt[i])


### FIXED CODE ###

import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])
### BUGGY CODE ###

import sys
from collections import deque, defaultdict


def topological_check(roots, out_links, in_counts):
    depth = {r: 1 for r in roots}
    q = deque(roots)
    while q:
        v = q.popleft()
        d = depth[v] + 1
        for u in out_links[v]:
            in_counts[u] -= 1
            if in_counts[u] == 0:
                depth[u] = d
                q.append(u)
    if any(in_counts.values()):
        return -1
    return max(depth.values())


n = int(input())
match_count = n * (n - 1) // 2

roots = set()
in_counts = defaultdict(lambda: 0)
out_links = defaultdict(set)

for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = i * n + j if i < j else j * n + i
    roots.add(prev)

    for j in aaa[1:]:
        key = i * n + j if i < j else j * n + i
        out_links[prev].add(key)
        in_counts[key] += 1
        prev = key

roots = {r for r in roots if in_counts[r] == 0}
print(topological_check(roots, out_links, in_counts))


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


n = int(input())
links = defaultdict(set)
may_root = set()
lines = sys.stdin.readlines()
matches = []
for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    match_order = []
    for j in aaa:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * n + b
        match_order.append(key)
    matches.append(match_order)
    may_root.add(match_order[0])

for i in range(n):
    kkk = matches[i]
    prev = kkk[0]

    for key in kkk[1:]:
        links[prev].add(key)
        may_root.discard(key)
        prev = key

if not may_root:
    print(-1)
    exit()

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))
### BUGGY CODE ###

count = 0
W = input().lower()
T = [0]
while True:
    try:
        if T[0] == "END_OF_TEXT":
            break
        for t in T:
            if W == t:
                count += 1
        T = [x.lower() for x in input().split()]
    except EOFError:
        break
    except IndexError:
        pass
print(count)

### FIXED CODE ###

count = 0
W = input().lower()
T = [0]
while True:
    try:
        if T[0] == "END_OF_TEXT":
            break
        for t in T:
            if W == t:
                count += 1
        T = [x.lower() for x in input().split()]
    except EOFError:
        break
    except IndexError:
        break
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque

N, M = tuple(map(int, input().split()))
adj = [[] for n in range(N)]

for _ in range(M):
    inp = tuple(map(int, input().split()))
    adj[inp[0]].append(inp[1])
    adj[inp[1]].append(inp[0])

unsearched = set(range(N))
colors = {n:-1 for n in range(N)}
color = -1
while len(unsearched):
    color += 1
    start = min(unsearched)
    unsearched.remove(start)
    searched = set([start])
    
    que = deque([start])
    while len(que):
        q = que.pop()
        next_ = [i for i in adj[q] if  not (i in searched)]
        searched.update(next_)
        unsearched = unsearched.difference(searched)
        que.extendleft(next_)
    for n in searched:
        colors[n] = color
    
Q = int(input())

for i in range(Q):
    question = tuple(map(int, input().split()))
    if colors[question[0]] == colors[question[1]]:
        print("yes")        
    else:
        print("no")

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

N, M = tuple(map(int, input().split()))
adj = [[] for n in range(N)]

for _ in range(M):
    inp = tuple(map(int, input().split()))
    adj[inp[0]].append(inp[1])
    adj[inp[1]].append(inp[0])

unsearched = set(range(N))
colors = {n:-1 for n in range(N)}
color = -1

for n in range(N):
    if colors[n] != -1:
        continue
    color += 1
    start = n
    
    que = deque([start])
    while len(que):
        q = que.pop()
        next_ = [i for i in adj[q] if colors[i] == -1]
        que.extendleft(next_)
        colors[q] = color
    
Q = int(input())

for i in range(Q):
    question = tuple(map(int, input().split()))
    if colors[question[0]] == colors[question[1]]:
        print("yes")        
    else:
        print("no")
### BUGGY CODE ###

s = input()

ans = 0
for i in range(1,len(s)):
  if s[i] == "W":
    a = s[:i].count("W")
    b = len(s[:i+1])
    ans += b - a - 1

print(ans)

### FIXED CODE ###

s = input()

ans = 0
for i in range(len(s)):
  if s[i] == "W":
    ans += i

a = 0
for i in range(s.count("W")):
  a += i

print(ans - a)
### BUGGY CODE ###

S = input()
N = len(S)
M = 10**9+7

case = [0] * 13
case[0] = 1
unit = 1
for i in reversed(range(N)):
    temp = [0] * 13
    if(S[i] == '?'):
        for j in range(10):
            increase = unit * j % 13
            for k in range(13):
                before = (k - increase) % 13
                temp[k] += case[before]
                temp[k] %= M
    else:
        num = int(S[i])
        increase = unit * num % 13
        for k in range(13):
            before = (k - increase) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13

print(case[5])


### FIXED CODE ###

S = input()
M = 10**9+7

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
# from bisect import *
# from collections import *
from heapq import *
# import itertools
import math
# INF = 10**9
# MOD = 10**9+7

N, K = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
f = [int(x) for x in input().split()]
f.sort(reverse = 1)
h = [(-x*y, x, y) for x, y in zip(a, f)]
heapify(h)
while K > 0:
    v, x, y = heappop(h)
    vn, xn, yn = h[0]
    xd = int(xn*yn/y)
    if xd*y == -vn:
        xd -= 1
    if x-xd <= K:
        K -= x-xd
        heappush(h, (-xd*y, xd, y))
    else:
        heappush(h, (-(x-K)*y, x-K, y))
        break
print(-h[0][0])


# cnt = defaultdict(int)
# for x in f:
#     cnt[x] += 1
# cnt.sort(key = lambda v : v[0])
# lst = defaultdict(list)
# l = 0
# for k, v in cnt:
#     lst[k] = Counter(a[l:l+cnt[k]])
#     l += cnt[k]
# h = [(cnt[k]*lst[k][-1][0], k) for k in cnt]
# h.heapify()
# while K > 0:
#     v, k = heappop(h)
#     if v == 0:
#         break


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
# from bisect import *
from collections import *
from heapq import *
# import itertools
import math
# INF = 10**9
# MOD = 10**9+7

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
F = [int(x) for x in input().split()]
F.sort(reverse = 1)
l, r = -1, 10**12
while l+1 < r:
    x = (l+r)//2
    c = 0
    for a, f in zip(A, F):
        if a*f > x:
            c += max(0,a-x//f)
    if c > K:
        l = x
    else:
        r = x
print(r)
### BUGGY CODE ###

s=input()

k = 10**100
logk = k.bit_length()
lens = len(s)
doubling = [[0]*lens for _ in range(logk)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

logs = lens.bit_length()
for i in range(1,logs):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

for i in range(lens):
  print(doubling[logs-1].count(i))


### FIXED CODE ###

s=input()

logk = (10**100).bit_length()
lens = len(s)
logs = lens.bit_length()
doubling = [[0]*lens for _ in range(logk)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

for i in range(1,logk):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

from collections import Counter
result = Counter(doubling[logk-1])
for i in range(lens):
  print(result[i])