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

def STR(): return '?' * pow(10, 5)#input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1

for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])


### FIXED CODE ###

def STR(): return input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1


for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])
### BUGGY CODE ###

def gcd(a,b):
    a,b=max(a,b),min(a,b)
    while b>0:
        a,b=b,a%b
    return(a)

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += gcd(i,gcd(j,k))
print(ans)


### FIXED CODE ###

import math
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)
### BUGGY CODE ###

N=int(input())
x=0
for n in range(1,N):
  a=N-n
  for s in range(1,a+1):
    if a % s == 0:
      x+=1
    else:
      x+=0
print(x)

### FIXED CODE ###

N=int(input())
x=0
for n in range(1,N):
  x+=(N-1)//n
print(x)
### BUGGY CODE ###

s = input()
q = int(input())
r = False
for _ in range(q):
    t = input().split()
    if len(t) == 1:
        r = not r
    else:
        t[1] = int(t[1]) - 1
        if (not t[1] and not r) or (t[1] and r):
            s = t[2] + s
        else:
            s = s + t[2]
if r:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
q = int(input())
r = False
for _ in range(q):
    t = input().split()
    if len(t) == 1:
        r = not r
    else:
        t[1] = int(t[1]) - 1
        if (not t[1] and not r) or (t[1] and r):
            S.appendleft(t[2])
        else:
            S.append(t[2])
if r:
    S = list(S)
    print(''.join(S[::-1]))
else:
    print(''.join(S))
### BUGGY CODE ###

def main():
    import numpy as np
    import sys
    input=sys.stdin.readline
    inf=10**11
    
    a,b,q=map(int,input().split())
    S=np.array([-inf]+[int(input()) for _ in range(a)]+[inf])
    T=np.array([-inf]+[int(input()) for _ in range(b)]+[inf])
    Q=np.array([int(input()) for _ in range(q)])
    idxs=np.searchsorted(S,Q)
    idxt=np.searchsorted(T,Q)
    
    for i in range(q):
        x=Q[i]
        s=idxs[i]
        t=idxt[i]
        ans=max(T[t],S[s])-x
        ans=min(ans,S[s]-T[t-1]+min(S[s]-x,x-T[t-1]))
        ans=min(ans,x-min(S[s-1],T[t-1]))
        ans=min(ans,T[t]-S[s-1]+min(T[t]-x,x-S[s-1]))
        print(ans)
        
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    INF=10**11
    from bisect import bisect_left
    a,b,q=map(int,input().split())
    S=[-INF]+[int(input()) for _ in range(a)]+[INF]
    T=[-INF]+[int(input()) for _ in range(b)]+[INF]

    for _ in range(q):
        x=int(input())
        s=bisect_left(S,x)
        t=bisect_left(T,x)
        ans=max(T[t],S[s])-x
        ans=min(ans,S[s]-T[t-1]+min(S[s]-x,x-T[t-1]))
        ans=min(ans,x-min(S[s-1],T[t-1]))
        ans=min(ans,T[t]-S[s-1]+min(T[t]-x,x-S[s-1]))
        print(ans)
if __name__=='__main__':
    main()
### BUGGY CODE ###

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    _, q = map(int, input().split())
    c = list(map(int, input().split()))

    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        ans.append(len(set(c[l-1:r])))

    for i in ans:
        print(i)

main()

### FIXED CODE ###

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()
### BUGGY CODE ###

N, C = map(int, input().split())
events = []
for i in range(N):
    events.append(list(map(int, input().split())))

dp = [[0]*2001 for i in range(C+1)]
for j in range(C+1):
    for k in range(-1000, 1001):
        if k != 0:
            dp[j][k] = -10**18
for a, b, c in events:
    for j in range(C-c, -1, -1):
        for k in range(-1000, 1001):
            if k + (b-a) >= -100:
                dp[j+c][k+b-a] = max(dp[j+c][k+b-a], dp[j][k] + a)
            if k + (a-b) <= 100:
                dp[j+c][k+a-b] = max(dp[j+c][k+a-b], dp[j][k] + b)
ans = 0
for j in range(C+1):
    for k in range(-1000, 1001):
        ans = max(ans, min(dp[j][k] + k, dp[j][k]))
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
events = []
for i in range(N):
    events.append(list(map(int, input().split())))

def solve():
    L = 250
    dp = [[-10**18]*(L+1) for i in range(C+1)]
    for j in range(C+1):
        dp[j][0] = 0
    for a, b, c in events:
        for j in range(C-c, -1, -1):
            for k in range(L+1):
                if k + (b-a) <= 0:
                    dp[j+c][a-k-b] = max(dp[j+c][a-k-b], dp[j][k]+k+b)
                else:
                    dp[j+c][k+b-a] = max(dp[j+c][k+b-a], dp[j][k]+a)
                if k + (a-b) <= L:
                    dp[j+c][k+a-b] = max(dp[j+c][k+a-b], dp[j][k]+b)
    ans = 0
    for j in range(C+1):
        ans = max(ans, max(dp[j]))
    return ans
print(solve())
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99775 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
L = np.zeros((10**6+10,))
used = set()
first = True
for a in A:
    if a in used and first:
        first = False
        L[::a] += 1
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)







### FIXED CODE ###

# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
#first = True  # firstのフラッグの使い回しをしていた．複数に分かれる条件分岐はしっかりとどのような分岐をするか書く癖をつけたほうがよい
for a in A:
    if L[a] == 2:
        continue
    if a in used:
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)
### BUGGY CODE ###

N,K = map(int,input().split())
A = []
for i in range(N):
    x,y = list(map(int,input().split()))
    a = [x] * y
    A += a
A.sort()
print(A[K - 1])

### FIXED CODE ###

from heapq import heappop,heappush
N,K = map(int,input().split())
A = []
for i in range(N):
    a = list(map(int,input().split()))
    heappush(A,a)
count = 0
while count < K:
    x,y = heappop(A)
    count += y
print(x)
### BUGGY CODE ###

# Editorial solution 4
import sys

def f(a, b, c, border, cond):
    cnt = 0
    for i in range(len(a)):
        for j in range(len(b)):
            for k in range(len(c)):
                if a[i] + b[j] + c[k] < border:
                    break
                cnt += 1
                if cnt >= cond:
                    return True
    return False


def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), key=lambda x: -x)
    B = sorted(list(map(int, input().split())), key=lambda x: -x)
    C = sorted(list(map(int, input().split())), key=lambda x: -x)

    l, r = A[X-1] + B[Y-1] + C[Z-1], A[0] + B[0] + C[0]
    while r - l > 1:
        p = (l + r) // 2
        if f(A, B, C, p, K):
            l = p
        else:
            r = p

    deli = []
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                if A[i] + B[j] + C[k] < r:
                    break
                deli.append(A[i] + B[j] + C[k])

    num = len(deli)
    deli = sorted(deli, key=lambda x: -x)
    deli += [l] * (K - num)
    for i in range(K):
        print(deli[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), key=lambda x: -x)
    B = sorted(list(map(int, input().split())), key=lambda x: -x)
    C = sorted(list(map(int, input().split())), key=lambda x: -x)

    deli = []
    heappush(deli, (-A[0]-B[0]-C[0], 0, 0, 0))
    pushed = set((0,0,0))
    for _ in range(K):
        d = heappop(deli)
        i, j, k = d[1], d[2], d[3]

        if i+1 < X and (i+1, j, k) not in pushed:
            heappush(deli, (-A[i+1]-B[j]-C[k], i+1, j, k))
            pushed.add((i+1, j, k))

        if j+1 < Y and (i, j+1, k) not in pushed:
            heappush(deli, (-A[i]-B[j+1]-C[k], i, j+1, k))
            pushed.add((i, j+1, k))

        if k+1 < Z and (i, j, k+1) not in pushed:
            heappush(deli, (-A[i]-B[j]-C[k+1], i, j, k+1))
            pushed.add((i, j, k+1))

        print(-d[0])


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

N, M = list(map(int, input().split()))
ABs = [0] * N

for i in range(N):
    a, b = list(map(int, input().split()))
    ABs[i] = (a, b)

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
        else:
            for i in range(day, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    break
result = sum(rewards)
print(result)

### FIXED CODE ###

N, M = list(map(int, input().split()))
ABs = [0] * N
day_dic = {}

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

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            day_dic[day] = day
            count += 1
        else:
            esti = day_dic.get(day)
            if esti is None:
                esti = day
            for i in range(esti, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    day_dic[day] = i
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)
### BUGGY CODE ###

h,w,a,b=map(int,input().split())
l=[(w-a)*i+a*(h-i) for i in range(h+1)]
for j in list(range(w))[::-1]:
  if (h-b)*j+b*(w-j) in l:
    x=l.index((h-b)*j+b*(w-j))
    y=j
    ans=[[0]*w for _ in range(h)]
    goalh=[w-a]*x+[a]*(h-x)
    goalw=[h-b]*y+[b]*(w-y)
    nowh=[0]*h
    noww=[0]*w
    for i in range(h):
      for j in range(w):
        if nowh[i]<goalh[i] and noww[j]<goalw[j]:
          ans[i][j]=1
          nowh[i]+=1
          noww[j]+=1
    if nowh!=goalh or noww!=goalw:
      continue
    for i in range(h):
      print(*ans[i],sep="")
    exit()
print("No")

### FIXED CODE ###

h,w,a,b=map(int,input().split())
for i in range(b):
  print(*([0]*a+[1]*(w-a)),sep="")
for i in range(h-b):
  print(*([1]*a+[0]*(w-a)),sep="")
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
e=list(range(1,n+1))
d=dict(zip(e,a))
f=sorted(d.items(), key=lambda x: x[1])
g=str(f[0][0])
for i in range(1,n):
    g = g + " " + str(f[i][0])
print(g)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
b=sorted(a)
c=[0]*n
for i in range(n):
    c[a[i]-1] = i+1
print(' '.join(map(str, c)))
### BUGGY CODE ###

N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
h=[0]
for i in range(N):
  if t[g[i]-1] in set(g):
    a=i+1
    h[0]=t[g[i]-1]
    break
  g.append(t[g[i]-1])
if K>a:
  for i in range(N):
    if t[h[i]-1] in set(h):
      break
    h.append(t[h[i]-1])
  b=i+1
  K=(K-a)%b+a-b
print(g[K])

### FIXED CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[np.inf]*n
dp[0]=0

for i in range(n):
  a=max(0,i-k)
  for j in range(a,i):
    dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp=[100000000000000000]*n
dp[0]=0
for i in range(1,n):
  for j in range(k):
    if i > j:
      dp[i] = min(dp[i],dp[i-j-1]+abs(h[i]-h[i-j-1]))
print(dp[-1])
### BUGGY CODE ###

import bisect

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

trees = []

for _ in range(N):
    item = int(input())
    trees.insert(bisect.bisect_left(trees, item), item)    

curmin = 1 + 10**9

for i in range(N-K+1):
    curmin = min(curmin, trees[i+K-1] - trees[i])

print(curmin)

### FIXED CODE ###

import heapq
import queue

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

trees = []
heapq.heapify(trees)

for _ in range(N):
    heapq.heappush(trees, int(input()))

ans = 1 + 10**9

q = queue.Queue(maxsize=K-1)

for _ in range(K-1):
    q.put(heapq.heappop(trees))

for _ in range(N-K+1):
    curmin = q.get()
    nextmin = heapq.heappop(trees)

    ans = min(ans, nextmin-curmin)

    q.put(nextmin)

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

# -*- coding: utf-8 -*-


def answer(S, T, N):
    i = 0
    while i < N:
        c1 = S[i]
        c2 = T[i]
        # print("c1:", str(c1))
        # print("c2:", str(c2))
        if c1 != c2:
            for j in range(N):
                # print([S[j], c1])
                # print([T[j], c2])
                if S[j] == c1 and T[j] != c2:
                    return False
        i += 1

    return True


S = list(input())
T = list(input())

N = len(S)

ST = [None] * N

for i in range(N):
    ST[i] = [S[i], T[i]]

ST.sort(key=lambda a_i: a_i[0])

for i in range(N):
    S[i] = ST[i][0]
    T[i] = ST[i][1]

ans1 = answer(S, T, N)

ST.sort(key=lambda a_i: a_i[1])

for i in range(N):
    S[i] = ST[i][0]
    T[i] = ST[i][1]

# print(S)
# print(T)

ans2 = answer(T, S, N)

if ans1 and ans2:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# coding: utf-8

# https://atcoder.jp/contests/abc110


def main():
    S = input()
    T = input()
    N = len(S)

    memo1 = {}
    memo2 = {}
    for i in range(N):
        if S[i] not in memo1:
            memo1[S[i]] = T[i]
        else:
            if memo1[S[i]] != T[i]:
                return "No"
        if T[i] not in memo2:
            memo2[T[i]] = S[i]
        else:
            if memo2[T[i]] != S[i]:
                return "No"

    return "Yes"


print(main())
### BUGGY CODE ###

import numpy as np

n = int(input())
A = np.array(list(map(int, input().split(' '))))

A_unique = np.unique(A)
num_dict = {}
total = 0
for a in A_unique:
  tmp = np.sum(A==a)
  num_dict[a] = (tmp*(tmp-1)/2, (tmp-1)*(tmp-2)/2)
  total += tmp*(tmp-1)/2

for k in range(n):
  print(int(total - num_dict[A[k]][0] + num_dict[A[k]][1]))
  

### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split(' ')))
 
c = dict(collections.Counter(A))
num_dict = {}
total = 0
for a, count in c.items():
  num_dict[a] = (count*(count-1)/2, (count-1)*(count-2)/2)
  total += count*(count-1)/2

ans_dict = {}
for a in c.keys():
  ans_dict[a] = total - num_dict[a][0] + num_dict[a][1]

for k in range(n):
  print(int(ans_dict[A[k]]))
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = [int(i) for i in input().split()]

L.sort()

num_triangles = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(a=L, x=L[i]+L[j], lo=j+1)        
        num_triangles += idx-(j+1) 
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import heapq

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

A = sorted(A)
F = sorted(F, reverse= True)
S = [(-A[i]*F[i], i) for i in range(N)]

heapq.heapify(S)

for i in range(K):
    ma = heapq.heappop(S)
    A[ma[1]] -= 1
    heapq.heappush(S, (-A[ma[1]]*F[ma[1]], ma[1]))

print(-heapq.heappop(S)[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import heapq

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

A = sorted(A)
F = sorted(F, reverse= True)
S = [(-A[i]*F[i], i) for i in range(N)]


def judge(s):
    global N, K
    ksum = 0
    for i in range(N):
        ksum += max(0, -(-(A[i] * F[i] - s) // F[i]))
    if ksum <= K:
        return True
    else:
        return False

lb = -1
ub = 10**13
while lb + 1 < ub:
    mid = (lb + ub) // 2
    if judge(mid):
        ub = mid
    else:
        lb = mid

print(ub)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
L = []
A.insert(0,0)
A.insert(N+1,0)
for i in range(1,N+1):
  k = 0
  L.append(A[i])
  del (A[i])
  for j in range(N):
    k += abs(A[j]-A[j+1])
  A.insert(i,L[i-1])
  print(k)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.insert(N+1,0)
S = 0
for i in range(N+1):
  S += abs(A[i]-A[i+1])
for i in range(1,N+1):
  print(S-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
Ps = [[] for _ in range(N)]
for i in range(M):
    j, Y = map(int,input().split())
    Ps[j-1].append([i,Y])
rets = [""]*M
for i_city,P in enumerate(Ps):
    if len(P)==0:
        continue
    
    inds = np.array(P)[:,0]
    years = np.array(P)[:,1]
    sorts = np.argsort(years)
    
    ## 降順/昇順に手こずりすぎ
    for i,(ind,s) in enumerate(zip(inds,sorts)):
        a = np.where(sorts==i)[0][0]
        rets[ind] = "{:06d}{:06d}".format(i_city+1,a+1)


for ret in rets:
    print(ret)

### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_left
N, M = map(int, input().split())
A = []
B = defaultdict(list)
 
for i in range(M):
    p, y = map(int, input().split())
    A.append([p, y])
    B[p].append(y)
 
for key in B.keys():
    B[key].sort()

# print(A,B)
# for a in A:
#     print(a[0],a[1],B[a[0]],bisect_left(B[a[0]],a[1]))
for a in A:
    print("%06d%06d" % (a[0], bisect_left(B[a[0]], a[1])+1))
### BUGGY CODE ###

N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

for i in starts:
    if i in goals:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

ans = set(starts) & set(goals)

if len(ans) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False


for i in range(Q):
    count = 0
    for j in range(l[i]-1,r[i]):
        if S[j] == 'A':
            flag = True
            continue
        if S[j] == 'C' and flag:
            count += 1
        flag = False
    print(count)


### FIXED CODE ###

N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False
ac = [0]*N
count = 0

for j in range(N):
        if S[j] == 'A':
            flag = True
            ac[j] = count
            continue
        if S[j] == 'C' and flag:
            count += 1
        ac[j] = count
        flag = False


for i in range(Q):
    print(ac[r[i]-1]-ac[l[i]-1])