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

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = list(list(map(int,input().split())) for i in range(M))
for B,C in BC:
    A.sort()
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = list(list(map(int,input().split())) for i in range(M))
A.sort()
BC = sorted(BC,key = lambda x:x[1],reverse = True)
X = []

for B,C in BC:
    for i in range(min(B,N-len(X))):
        X.append(C)
ans = [sum(A)]
p = len(X)
for i in range(p):
    ans.append(ans[-1]+X[i]-A[i])
print(max(ans))
### BUGGY CODE ###

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

for base in range(1, M//N+1)[::-1]:
    if M % base != 0:
        continue
    print(base)
    break


### FIXED CODE ###

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

for base in range(1, M//N+1)[::-1]:
    if M % base != 0:
        continue
    print(base)
    break
### BUGGY CODE ###

X = int(input())
L = [sum(range(i+1)) for i in range(X+1) if sum(range(i+1))<X]
print(len(L))

### FIXED CODE ###

X = int(input())
for i in range(X+1):
    if (i*(i+1)/2) >= X:
        time = i
        break
print(time)
### BUGGY CODE ###

x=int(input())

ans=1
for b in range(x):
    for p in range(2,x):
        if b**p <= x:
            ans=max(ans,b**p)
print(ans)

### FIXED CODE ###

x=int(input())

ans=1
for b in range(x):
    for p in range(2,x):
        if b**p <= x:
            ans=max(ans,b**p)
        else:
            break
print(ans)
### BUGGY CODE ###

import math
const=3500+1
N = int(input())
ans=4/N
flg=False
for h in range(1,const):
    for n in range(h,const):
        tmp=4*h*n-N*n-N*h
        if tmp != 0:
            w = N*h*n/tmp
            if w == int(w) and w>0:
                print(h,n,int(w) )
                flg=True
                break
    if flg==True:
        break



### FIXED CODE ###

import math
const=3500+1
N = int(input())
ans=4/N
flg=False
for h in range(int(N/4),const):
    for n in range(h,const):
        tmp=4*h*n-N*n-N*h
        if tmp != 0:
            w = N*h*n/tmp
            if w == int(w) and w>0:
                print(h,n,int(w) )
                flg=True
                break
    if flg==True:
        break
### BUGGY CODE ###

l,r=map(int,input().split())
if l==0:
    print(0)
elif r*(r-1)<2019:
    print(l*(l+1))
else:
    print(min(i*j%2019 for i in range(l,r) for j in range(i+1,r+1)))

### FIXED CODE ###

l,r=map(int,input().split())
if l==0:
    print(0)
elif r*(r-1)<2019:
    print(l*(l+1))
else:
    ans=2018
    for i in range(l,r):
        for j in range(i+1,r+1):
            if i*j%2019<ans:
                ans=i*j%2019
            elif i*j%2019==ans:
                print(ans)
                exit()
    print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]
if 1 not in a:
    dp.append(1)
else:
    dp.append(0)

for i in range(2, N + 1):
    if i not in a:
        dp.append((dp[i - 1] + dp[i - 2]) % mod)
    else:
        dp.append(0)

print(dp[-1])

### FIXED CODE ###

import collections
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = collections.deque([])
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]

if len(a) > 0:
    if 1 != a[0]:
        dp.append(1)
    else:
        dp.append(0)
        a.popleft()
else:
    dp.append(1)

for i in range(2, N + 1):
    if len(a) > 0:
        if i != a[0]:
            tmp = dp[0] + dp[1]
        else:
            tmp = 0
            a.popleft()
    else:
        tmp = dp[0] + dp[1]
    dp[0] = dp[1]
    dp[1] = tmp

print(dp[-1] % mod)
### BUGGY CODE ###

import sys
import pdb
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,Q = map(int, input().split())
    S = input().rstrip()
    ans = [0]*Q
    for q in range(Q):
        l,r = map(int, input().split())
        cnt = 0
        for i in range(l-1,r-1):
            if S[i:i+2] == 'AC': cnt += 1
        print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import pdb
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,Q = map(int, input().split())
    S = input().rstrip()
    dp = [0]*(N+1)
    for i in range(1,N):
        if S[i-1:i+1] == 'AC':
            dp[i+1] = dp[i]+1
        else:
            dp[i+1] = dp[i]
    for _ in range(Q):
        l,r = map(int, input().split())
        print(dp[r]-dp[l])

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

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離に変更
from collections import deque

H, W = list(map(int, input().split()))
all_count = H * W
L = [input() for i in range(H)]

reached = [[-1]*W for i in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if L[i][j] == "#":
      reached[i][j] = 0
      q.append((i, j))

cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
  i, j = q.popleft()
  for ch, cw in cands:
    nh, nw = i + ch, j + cw
    if nh < 0 or nh >= H or nw < 0 or nw >= W:
      continue
    if reached[nh][nw] == -1:
      reached[nh][nw] = reached[i][j] + 1
      q.append((nh, nw))
    elif reached[nh][nw] > reached[i][j]:
      reached[nh][nw] = reached[i][j] + 1

result = max([max(reached[i]) for i in range(H)])
print(result)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

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

for i in range(1, n+1):
    print(A.count(i))


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0]*n

for i in A:
    B[i-1] += 1

for i in B:
    print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

# pn = deque()
# pn.append(1)
A = 3234566668
count = 0
for L in range(1, A):
    str_L = str(L)
    chk = True
    for left in range(len(str_L) - 1):
        if abs(int(str_L[left]) - int(str_L[left + 1])) > 1:
            chk = False
            break

    if chk:
        # pn.append(L)
        count += 1
        if count == K:
            ans = L
            break


print(ans)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

K = input_int()

if K < 10:  # 1桁の数はすべてlun_lun
    print(K)
else:  # 桁数の小さいものからlun_lun数を生成し，queueに加えていく
    dq = deque([i for i in range(1, 10)])
    count = 0
    while True:
        x = dq.popleft()
        count += 1
        if count == K:
            print(x)
            exit()
        d = x % 10
        if d != 0:
            dq.append(10 * x + d - 1)
        dq.append(10 * x + d)
        if d != 9:
            dq.append(10 * x + d + 1)
### BUGGY CODE ###

n=int(input())

t = list(map(int,input().split()))

ans = 0
    
for i in range(n-1):
    for j in range(i+1,n):
        if j-i == t[i]+t[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n=int(input())

t = list(map(int,input().split()))

ans = 0

sa = [0]*(n+1)

for i in range(n):
    if i+1-t[i] > 0:
        sa[i+1-t[i]] += 1

for i in range(n):
    if 0 < i+1+t[i] < n:
        ans += sa[i+1+t[i]]
    if i+1-t[i] > 0:
        sa[i+1-t[i]] -= 1
print(ans)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
a_cakes = list(map(int, input().split()))
b_cakes = list(map(int, input().split()))
c_cakes = list(map(int, input().split()))
a_b_cakes = []
for a in a_cakes:
  for b in b_cakes:
    a_b_cakes.append(a+b)
a_b_cakes.sort(reverse=True)
a_b_c_cakes = []
for a_b in a_b_cakes[:K]:
  for c in c_cakes:
    a_b_c_cakes.append(a_b+c)
a_b_c_cakes.sort(reverse=True)
for ans in a_b_c_cakes[:K]:
  print(ans)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
a_cakes = list(map(int, input().split()))
b_cakes = list(map(int, input().split()))
c_cakes = list(map(int, input().split()))
a_b_cakes = []
for a in a_cakes:
  for b in b_cakes:
    a_b_cakes.append(a+b)
a_b_cakes.sort(reverse=True)
a_b_c_cakes = []
for a_b in a_b_cakes[:K]:
  for c in c_cakes:
    a_b_c_cakes.append(a_b+c)
a_b_c_cakes.sort(reverse=True)
for ans in a_b_c_cakes[:K]:
  print(ans)
### BUGGY CODE ###

K = int(input())
ans = 0

def gcd(nums):
    while True:
        gcd = 30000
        min_idx = -1
        c = 0
        for i in range(3):
            if 0 < nums[i] < gcd:
                gcd = nums[i]
                min_idx = i
        for i in range(3):
            nums[i] %= gcd
            if nums[i] > 0: c += 1
        if c == 0:
            return gcd
        else:
            nums[min_idx] = gcd

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += gcd([i, j, k])

print(ans)

### FIXED CODE ###

K = int(input())
ans = 0

def gcd(x, y):
    if x < y: x, y = y, x
    while y:
        n = x%y
        x = y
        y = n
    return x
    
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ret = gcd(i, j)
            ans += gcd(ret, k)

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

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*10**(i-1)) % 2019  # ここでmodしておく
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for value in c.values():
    ans += value*(value-1)//2
print(ans)






### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)
### BUGGY CODE ###



def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    H,W=MI()
    A=[["#"]*(W+2)for _ in range(H+2)]
    
    for i in range(H):
        S=input()
        for j in range(W):
            A[i+1][j+1]=S[j]
    
    
    
    import queue
    q=queue.Queue()
    
    inf=-1
    dMap=[[inf]*(W+2)for _ in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
                dMap[i][j]=0
                
    for i in range(H+2):
        dMap[i][0]=0
        dMap[i][-1]=0
        
    for j in range(W+2):
        dMap[0][j]=0
        dMap[-1][j]=0
        
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if dMap[nxt_i][nxt_j]==inf:
                q.put((nxt_i,nxt_j,d+1))
                dMap[nxt_i][nxt_j]=d+1
         
                
    ans=0
    for i in range(H+2):
        temp=max(dMap[i])
        ans=max(temp,ans)
    print(ans)
                
                
    
            

main()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

black_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

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

X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = []
A.sort()
B.sort()
C.sort()
for i in A:
    for j in B:
       DD.append(i+j)
DD.sort()
F = [(i+j)
     for i in DD[max(len(DD)-3010,0):]
     for j in C
]
F.sort()
for i in range(K):
    print(F[-1-i])
        


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline
X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = [i+j for i in A for j in B]
DD.sort()
heap = []
for i in DD[max(len(DD)-3001,0):]:
     for j in C:
         heapq.heappush(heap,-(i+j))
for i in range(K):
    print(-heapq.heappop(heap))
### BUGGY CODE ###

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

def popMaxOishisa(sushis):
    t, d = sushis.pop()
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    if len(sel_sushis["min"]) == 0:
        return -1, -1
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"].pop(t)
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    t, d = -1, -1
    while True:
        t, d = sushis.pop()
        if not t in netas:
            break
    return t, d


n, k = map(int, input().split())

# Store data
sushis = []
neta_set = set()
sel_sushis = {}
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    if t1 < 0:
        break
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)


### FIXED CODE ###

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


n, k = map(int, input().split())

# Store data
sushis = []
neta_set = set()
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)


# Select sushi set as maximum oishisa point
sel_sushis = []
neta_set = set()
sum_oishisa = 0
for i in range(k):
    t, d = sushis.pop()
    if t in neta_set:
        sel_sushis.append((t,d))
    else:
        neta_set.add(t)
    sum_oishisa += d

sel_sushis.sort(key=lambda i:i[1], reverse=True)
tMin = len(neta_set)
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    if len(sel_sushis) == 0:
        break
    t1, d1 = sel_sushis.pop()
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    while True:
        t2, d2 = sushis.pop()
        if not t2 in neta_set:
            break

    sum_oishisa += d2
    neta_set.add(t2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)
### BUGGY CODE ###

s = input()
q = int(input())

rev = 0
for _ in range(q):
    query = list(input().split())
    if query[0] == "1":
        rev = 1 if rev == 0 else 0
    else:
        if query[1] == "1":
            if rev == 0:
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if rev == 0:
                s = s + query[2]
            else:
                s = query[2] + s
if rev == 1:
    new_s = ''.join(list(reversed(s)))
    print(new_s)
else:
    print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

rev = False
for _ in range(q):
    query = list(input().split())
    t = query[0]
    if t == "1":
        rev = not rev
    else:
        f = int(query[1])
        c = query[2]
        if rev:
            f = 3 - f
        if f == 1:
            s.appendleft(c)
        else:
            s.append(c)
if rev:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
import math
import heapq


def solve(N: int, K: int, A: "List[int]", F: "List[int]"):
    h = []
    A.sort()
    F.sort(reverse=True)
    for a, f in zip(A, F):
        heapq.heappush(h, (-a*f, a, f))
    k = K
    while k > 0:
        p1, a1, f1 = heapq.heappop(h)
        p2, a2, f2 = heapq.heappop(h)
        p1, p2 = -p1, -p2
        sub = min(a1 - math.ceil((p2/f1)-1), k)
        a1 -= sub
        k -= sub
        heapq.heappush(h, (-a1*f1, a1, f1))
        heapq.heappush(h, (-a2*f2, a2, f2))
    # print(h)
    p, a, f = heapq.heappop(h)
    print(-p)

    return


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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    F = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A, F)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
from bisect import bisect_left


def solve(N: int, K: int, A: "List[int]", F: "List[int]"):
    A.sort()
    F.sort(reverse=True)
    h = []
    for a, f in zip(A, F):
        h.append((a*f, a, f))
    h.sort()
    maxtime = h[-1][0]

    def isOK(y):
        i = bisect_left(h, (y+1, -1, -1))
        counter = 0
        # print(h[i:])
        for p, a, f in h[i:]:
            counter += a-y//f
        return counter <= K

    def binary_search(x):
        ng = -1
        ok = len(x)
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            # print("mid: {}, in ({}, {})".format(mid, ng, ok))
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    ng, ok = binary_search(range(maxtime))
    print(ok)

    # while k > 0:
    #     p1, a1, f1 = heapq.heappop(h)
    #     p2, a2, f2 = heapq.heappop(h)
    #     p1, p2 = -p1, -p2
    #     sub = min(a1 - math.ceil((p2/f1)-1), k)
    #     a1 -= sub
    #     k -= sub
    #     heapq.heappush(h, (-a1*f1, a1, f1))
    #     heapq.heappush(h, (-a2*f2, a2, f2))
    # # print(h)
    # p, a, f = heapq.heappop(h)
    # print(-p)

    return


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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    F = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A, F)


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

import collections as cl
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

cnt = cl.Counter(A)
ans = 0

for a in A:
    ans = 0
    cnt[a] -= 1
    for v in cnt.values():
        if v < 2:
            continue
        ans += combinations_count(v, 2)
    cnt[a] += 1
    print(ans)


### FIXED CODE ###

import collections as cl
import math


def combinations_count(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

cnt = cl.Counter(A)
ans = 0
for v in cnt.values():
    ans += combinations_count(v, 2)

for a in A:
    print(ans - cnt[a]+1)
### BUGGY CODE ###

import bisect

def main():
    N = int(input())
    P = list(map(int, input().split()))

    ans = 0

    while len(P) != 0:
        m = min(P)
        i = P.index(m)
        P = P[0:i]
        ans += 1


    print(ans)

    return 0

if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))


    ans = 1
    f = P[0]

    for i in range(1, N):
        f_o = P[i]
        if f >= f_o:
            ans+=1
            f = f_o
    print(ans)
    return 0


if __name__ == '__main__':
    main()