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

s = input()
x, y = map(int, input().split())

s2 = s.split('T')
sXs = list(map(len, s2[0::2]))
sYs = list(map(len, s2[1::2]))

memoX = [{sXs[0]}, set()]
for i, sX in enumerate(sXs[1:]):
    memoX[1 - i % 2] = set()
    for p in memoX[i % 2]:
        memoX[1 - i % 2].add(p + sX)
        memoX[1 - i % 2].add(p - sX)

memoY = [{0}, set()]
for i, sY in enumerate(sYs):
    memoY[1 - i % 2] = set()
    for p in memoY[i % 2]:
        memoY[1 - i % 2].add(p + sY)
        memoY[1 - i % 2].add(p - sY)

if x in memoX[1 - len(sXs) % 2] and y in memoY[len(sYs) % 2]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())

s2 = s.split('T')
sXs = list(map(len, s2[0::2]))
sYs = list(map(len, s2[1::2]))

memoX = [{sXs[0]}, set()]
for i, sX in enumerate(sXs[1:]):
    memoX[1 - i % 2] = set()
    for p in memoX[i % 2]:
        memoX[1 - i % 2].add(p + sX)
        memoX[1 - i % 2].add(p - sX)

memoY = [{0}, set()]
for i, sY in enumerate(sYs):
    memoY[1 - i % 2] = set()
    for p in memoY[i % 2]:
        memoY[1 - i % 2].add(p + sY)
        memoY[1 - i % 2].add(p - sY)

if x in memoX[1 - len(sXs) % 2] and y in memoY[len(sYs) % 2]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def ABC070D():
    N = int(input())
    abc = [list(map(int, input().split())) for i in range(N - 1)]
    ab = [[10000000000000 for i in range(N)] for j in range(N)]
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    for i, j, k in abc:
        ab[i - 1][j - 1] = k
        ab[j - 1][i - 1] = k

    for k in range(N):
        for i in range(N):
            for j in range(N):
                ab[i][j] = min(ab[i][j], ab[i][k] + ab[k][j])

    for x, y in xy:
        print(ab[x - 1][K - 1] + ab[K - 1][y - 1])
ABC070D()

### FIXED CODE ###

def ij2str(i, j):
    return str(i) + '+' + str(j)

n = int(input())
tree = [[] for _ in range(n)]
dis = [0 for _ in range(n)]
c_list = {}
visited = set()
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    c_list[ij2str(a-1, b-1)] = c
    c_list[ij2str(b-1, a-1)] = c

from collections import deque

q, k = map(int, input().split())
visited.add(k-1)
next = deque()
next.append(k-1)

while len(next):
    i = next.popleft()
    for j in tree[i]:
        if not j in visited:
            dis[j] = dis[i] + c_list[ij2str(i, j)]
            next.append(j)
            visited.add(j)

for i in range(q):
    x, y = map(int, input().split())
    print(dis[x-1] + dis[y-1])
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*(10 ** 9)+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod


ans = pow(2, n, mod) - 1 - comb(n, a) - comb(n, b)
if ans < 0:
    ans += mod

print(ans)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*(10 ** 5)+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    z = 1
    for i in range(n-r+1, n+1):
        z *= i
        z %= mod
    return (z * pow(f[r], mod-2, mod)) % mod

ans = (pow(2, n, mod) - 1 - comb(n, a) - comb(n, b)) % mod

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

import numpy as np
N=int(input())
A = list(map(int,input().split()))
G = [[int(i in (j,(j+1)%N)) for i in range(N)] for j in range(N)]
kakudai = np.array(G)
X=np.linalg.solve(G,A)
print(*[int(x*2) for x in X])

### FIXED CODE ###

N=int(input())
A = [int(i) for i in input().split()]
Rzero = sum(A)
#雨[0]を求める
for i in range(1,N,2):
    Rzero -= A[i]*2
Rain = [0]*N
Rain[0] = Rzero
for i in range(1,N):
    Rain[i] = (2*A[i-1] - Rain[i-1])
print(*Rain)
### BUGGY CODE ###

import collections
import sys
sys.setrecursionlimit(10**7)

def calc(one,two,three):
  if dp[one][two][three]!=-1:
    return dp[one][two][three]
  zero=n-one-two-three
  ret=0
  if zero!=n:
    ret=1/(1-zero/n)
  if one!=0:
    ret+=(calc(one-1,two,three)*one/n)/(1-zero/n)
  if two!=0:
    ret+=(calc(one+1,two-1,three)*two/n)/(1-zero/n)
  if three!=0:
    ret+=(calc(one,two+1,three-1)*three/n)/(1-zero/n)
  dp[one][two][three]=ret
  return ret

n=int(input())
arr=list(map(int,input().split()))
dp=[[[-1]*301 for _ in range(301)] for _ in range(301)]
cnt=[0,0,0,0]
for val in arr:
  cnt[val]+=1
calc(cnt[1],cnt[2],cnt[3])
print(dp[cnt[1]][cnt[2]][cnt[3]])

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
cnt=collections.Counter(arr)
for total in range(1,n+1):
  for three in range(total+1):
    for two in range(total-three+1):
      one=total-two-three
      dp[one][two][three]+=n/total
      if one!=0:
        dp[one][two][three]+=dp[one-1][two][three]*one/total
      if two!=0:
        dp[one][two][three]+=dp[one+1][two-1][three]*two/total
      if three!=0:
        dp[one][two][three]+=dp[one][two+1][three-1]*three/total
print(dp[cnt[1]][cnt[2]][cnt[3]])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    dp = [float("inf")] * N
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, N):
        for k in range(1, K+1):
            if i - k < 0:
                continue
            dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))

    print(dp[-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    dp = [float("inf")] * N
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, N):
        for k in range(1, K+1):
            if i - k < 0:
                continue
            dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))

    print(dp[-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)


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

N=int(input())
A=list(map(int,input().split()))
print(min(abs(sum(A[:i])-sum(A[i:])) for i in range(1,N)))

### FIXED CODE ###

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

a,b,k = map(int, input().split())
l = []
for i in range(b-a+1):
    l.append(a+i)
#print(l)
c = len(l)
d = min(c,k)
x = []
for j in range(d):
    x.append(l[j])
    x.append(l[-(j+1)])

x = list(set(x))
print(*sorted(x), sep='\n')


### FIXED CODE ###

a,b,k = map(int, input().split())
#print(l)
c = b-a+1

x = []
if k*2 > c:
    for i in range(a, b+1):
        x.append(i)
else:
    for j in range(a, a+k):
        x.append(j)
    for j in range(b-k+1, b+1):
        x.append(j)

print(*sorted(x), sep='\n')
### BUGGY CODE ###

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

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

### FIXED CODE ###

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

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

n = int(input())
for a in range(1,3501):
  for b in range(1,3501):
    s = n*a*b
    #s=4
    t = 4*a*b-n*b-n*a
    #t=8-4-2
    if t!=0 and s%t==0 and t>0:
      c = s//t
      print(a,b,c)
      exit()

### FIXED CODE ###

n = int(input())
if n<=3000:
  for a in range(1,3501):
    for b in range(1,3501):
      s = n*a*b
      #s=4
      t = 4*a*b-n*b-n*a
      #t=8-4-2
      if s<=t*3500:
        if t!=0 and s%t==0 and t>0:
          c = s//t
          print(a,b,c)
          exit()
else:
  for a in range(3501,1,-1):
    for b in range(3501,1,-1):
      s = n*a*b
      #s=4
      t = 4*a*b-n*b-n*a
      #t=8-4-2
      if s<=t*3500:
        if t!=0 and s%t==0 and t>0:
          c = s//t
          print(a,b,c)
          exit()
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    p10 = pow(10, i - 1, 13)
    if s != '?':
        for k in range(13):
            dp[i][(int(s) * p10 + k) % 13] += dp[i - 1][k]
            dp[i][(int(s) * p10 + k) % 13] %= MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i][(j * p10 + k) % 13] += dp[i - 1][k]
                dp[i][(j * p10 + k) % 13] %= MOD

print(dp[N][5] % MOD)


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)


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

n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  a, b = data[i]
  if a not in d1:
    d1[a] = []
  d1[a].append(b)
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
  else:
    if len(d2) == 0:
      continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
print(result)


### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
n=int(input())
a= list(map(int, input().split()))
ans=1
for i in range(n):
    ans*=a[i]

if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
n=int(input())
a= list(map(int, input().split()))
ans=1
if 0 in a:
    print(0)
    sys.exit()
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        sys.exit()

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

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))
### BUGGY CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, 3001):
    balls = R*r
    if N < balls:
        break
    for g in range(0, 3001):
        balls = R*r + G*g
        if N < balls:
            break
        left = N - balls
        if left % B == 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
rsum = 0
for r in range(0, N+1):
    if N < rsum:
        break
    rgsum = rsum
    for g in range(0, N+1):
        if N < rgsum:
            break
        left = N - rgsum
        if left % B == 0:
            ans += 1
        rgsum += G
    rsum += R

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

_,s=open(0);a=s.count('.'),
for i in s:a+=a[-1]+(i<'.'or-1),
print(min(a))

### FIXED CODE ###

_,s=open(0);c=s.count('.');a=[c]
for i in s:c+=i<'.'or-1;a+=c,
print(min(a))
### BUGGY CODE ###

# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

from fractions import gcd

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans = (ans + c // x) % MOD

print(ans)


### FIXED CODE ###

# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

MAX = max(p) + 1

inv = [0]+[1]
for i in range(2,MAX + 1):
    inv += [inv[MOD % i] * (MOD - MOD // i) % MOD]

prime = [0 for i in range(MAX)]

max_map = dict()


# function to return a^n
def power(a, n):
    if n == 0:
        return 1
    p = power(a, n // 2) % MOD
    p = (p * p) % MOD

    if n & 1:
        p = (p * a) % MOD
    return p


# function to find the smallest prime
# factors of numbers upto MAX
def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

        # function to return the LCM MODulo M


def lcmModuloM(arr, n):
    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:
        # LCM is product of primes to their
        # higest powers MODulo M
        ans = (ans * power(i, max_map[i])) % MOD
    return ans

sieve()
c = lcmModuloM(p, n)

ans = 0
for x in p:
    ans = (ans + c * inv[x]) % MOD

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

S = input()
Q = int(input())

t = 1
for i in range(Q):
    A = input()
    if A=="1":
        t*=-1
    else:
        AL = list(A.split())
        if AL[1]=="1":
            if t==1:
                S = AL[2]+S
            else:
                S = S+AL[2]
        elif AL[1]=="2":
            if t==1:
                S = S+AL[2]
            else:
                S = AL[2]+S

if t==-1:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
B = []
C = []
t = 1
for i in range(Q):
    A = input()
    if A=="1":
        t*=-1
    else:
        AL = list(A.split())
        if AL[1]=="1":
            if t==1:
                B.append(AL[2])
            else:
                C.append(AL[2])
        elif AL[1]=="2":
            if t==1:
                C.append(AL[2])
            else:
                B.append(AL[2])

B = ''.join(B)
C = ''.join(C)

if t==-1:
    print(C[::-1]+S[::-1]+B)
else:
    print(B[::-1]+S+C)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())
L = list(map(int, input().split()))
res = 0
def dfs(A):
    global res, L
    ans = [i for i, v in enumerate(A) if v == 1]
    if len(A) == N:
        if len(ans) == 3:
            a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
            if a < (b + c) and b < (c + a) and c < (a + b):
                res += 1
        return
    elif len(ans) == 3:
        a, b, c = L[ans[0]], L[ans[1]], L[ans[2]]
        if a < (b + c) and b < (c + a) and c < (a + b):
            res += 1
        return
    else:
        for v in range(2):
            A.append(v)
            dfs(A)
            A.pop()
dfs([])
print(res)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
for a_i in range(N-2):
    for b_j in range(a_i+1, N-1):
        c_idx = bisect.bisect_left(L, L[a_i]+L[b_j])
        if c_idx > b_j:
            ans += c_idx - b_j - 1
print(ans)
### BUGGY CODE ###

from itertools import combinations
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10**9+7
ans = 0
for i in combinations(a,k):
    ans += i[k-1] - i[0]

print(ans%mod)

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10**9+7
fac = [0]*(n+1)
finv = [0]*(n+1)
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac[0] = finv[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)
smin = 0
smax = 0
for i in range(n):
    smin += (a[i]*comb(n-i-1,k-1))%mod
    smin %= mod
    smax += (a[n-1-i]*comb(n-i-1,k-1))%mod
    smax %= mod
ans = (smax-smin)%mod
print(ans)
### BUGGY CODE ###

import re

def my_solve1():
    N, Q = map(int, input().split())
    # print(N, Q)
    acgt_string = input()
    sub_str_ith = []
    for _ in range(Q):
        start, end = map(int, input().split())
        sub_str_ith.append((start, end))
    # print(sub_str_ith)

    # 全ての'A'の位置を取得
    a_iths = [m.span() for m in re.finditer('AC', acgt_string)]
    # print(a_iths)

    for start, end in sub_str_ith:
        # print(start, end)
        num = 0
        for ac_start, ac_end in a_iths:
            if ac_start >= start-1 and ac_end <= end:
                num += 1
        print(num)
    

my_solve1()

### FIXED CODE ###

import re

def solve1():
    N, Q = map(int, input().split())
    # print(N, Q)
    acgt_string = input()
    sub_str_ith = []
    for _ in range(Q):
        start, end = map(int, input().split())
        sub_str_ith.append((start, end))

    t = [0] * (N+1)
    for i in range(N):
        t[i+1] = t[i] + (1 if acgt_string[i:i+2] == "AC" else 0)

    for start, end in sub_str_ith:
        print(t[end-1] - t[start-1])

def my_solve1():
    N, Q = map(int, input().split())
    # print(N, Q)
    acgt_string = input()
    sub_str_ith = []
    for _ in range(Q):
        start, end = map(int, input().split())
        sub_str_ith.append((start, end))
    # print(sub_str_ith)

    # 全ての'A'の位置を取得
    a_iths = [m.span() for m in re.finditer('AC', acgt_string)]
    # print(a_iths)

    for start, end in sub_str_ith:
        # print(start, end)
        num = 0
        for ac_start, ac_end in a_iths:
            if ac_start >= start-1 and ac_end <= end:
                num += 1
        print(num)


solve1()
# my_solve1()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
def solve():
  n,k = (int(i) for i in input().split())
  a = sorted(list(int(i) for i in input().split()))
  f = sorted(list(int(i) for i in input().split()),reverse = True)
  if sum(a) <= k:
    print(0)
    exit()
  
  ng = 0
  ok = 10**15

  while ok-ng >1 :
    next = (ok+ng)//2
    #a*fの値がnext以下になるか判定する
    tmpk = k
    for i in range(n):
      ta = a[i]
      tf = f[i]
      if ta*tf > next:
        tmpk -= math.ceil((ta*tf-next)/tf)
    if tmpk < 0:
       ng = next
    else:
       ok = next
  print(ok)
    
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math
def solve():
  n,k = (int(i) for i in input().split())
  a = sorted(list(int(i) for i in input().split()))
  f = sorted(list(int(i) for i in input().split()),reverse = True)
  if sum(a) <= k:
    print(0)
    exit()
  
  ng = 0
  ok = 10**15

  while ok-ng >1 :
    next = (ok+ng)//2
    #a*fの値がnext以下になるか判定する
    tmpk = k
    for i in range(n):
      ta = a[i]
      tf = f[i]
      if ta*tf > next:
        tmpk -= math.ceil((ta*tf-next)/tf)
    if tmpk < 0:
       ng = next
    else:
       ok = next
  print(ok)
    
solve()