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

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.append((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])
### BUGGY CODE ###

H, W = [int(_) for _ in input().split()]
S = []
for _ in range(H):
    S += [1 if _ == '.' else 0 for _ in list(input())]
S += [0] * W
SL = S.copy()
SR = S.copy()
SU = S.copy()
SD = S.copy()
for h in range(H):
    for i in range(W * h + 1, W * (h + 1)):
        if SL[i]:
            SL[i] = SL[i - 1] + 1
        else:
            SL[i] = 0
for h in range(H):
    for i in range(W * h - 2, W * (h - 1) - 1, -1):
        if SR[i]:
            SR[i] = SR[i + 1] + 1
        else:
            SR[i] = 0
for w in range(W):
    for i in range(W + w, W * H + w, W):
        if SU[i]:
            SU[i] = SU[i - W] + 1
        else:
            SU[i] = 0
for w in range(W):
    for i in range(W * (H - 2) + w - 1, -1, -W):
        if SD[i]:
            SD[i] = SD[i + W] + 1
        else:
            SD[i] = 0
score = 0
print(max((SL[_] + SR[_] + SU[_] + SD[_] - 3 for _ in range(H * W))))


### FIXED CODE ###

import copy
H, W = [int(_) for _ in input().split()]
S = []
for _ in range(H):
    S += [1 if _ == '.' else 0 for _ in list(input())]
S += [0] * W
SL = copy.copy(S)
SR = copy.copy(S)
SU = copy.copy(S)
SD = copy.copy(S)
for h in range(H):
    for i in range(W * h + 1, W * (h + 1)):
        if SL[i]:
            SL[i] = SL[i - 1] + 1
        else:
            SL[i] = 0
for h in range(H):
    for i in range(W * h - 2, W * (h - 1) - 1, -1):
        if SR[i]:
            SR[i] = SR[i + 1] + 1
        else:
            SR[i] = 0
for w in range(W):
    for i in range(W + w, W * H + w, W):
        if SU[i]:
            SU[i] = SU[i - W] + 1
        else:
            SU[i] = 0
for w in range(W):
    for i in range(W * (H - 2) + w - 1, -1, -W):
        if SD[i]:
            SD[i] = SD[i + W] + 1
        else:
            SD[i] = 0
score = 0
print(max((SL[_] + SR[_] + SU[_] + SD[_] - 3 for _ in range(H * W))))
### 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()))

a.sort()

tmp=0
cnt=0

for bangou in range(1,n+1):
    if tmp<len(a):
        while a[tmp]==bangou:
            cnt+=1
            tmp+=1
            if tmp==len(a):
                break
    print(cnt)
    cnt=0
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    for (li, ri) in zip(l, r):
        print(S[li - 1 : ri].count("AC"))


# 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
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    table = [0] * (N + 1)

    for i in range(N):
        table[i + 1] = table[i] + (1 if S[i : i + 2] == "AC" else 0)

    for i in range(Q):
        print(table[r[i] - 1] - table[l[i] - 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
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

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

from functools import cmp_to_key
import heapq
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(0,len(A)):
    B.append((A[i],i+1))
B.sort()
st = ""
for i in B:
    st = st + " " + str(i[1])
print(st[1:])

### FIXED CODE ###

from functools import cmp_to_key
import heapq
N = int(input())
A = list(map(int,input().split()))
B = [(A[i],i+1) for i in range(0,len(A))]
B.sort()
print(' '.join([str(n[1]) for n in B]))
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 1
if(0 in a):
  ans = 0
else:
  for i in range(N):
    ans *= a[i]
    if(ans>10**18):
      ans = -1
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 1
if(0 in a):
  ans = 0
else:
  for i in range(N):
    ans*=a[i]
    if(ans>10**18):
      ans = -1
      break
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])


ab.sort(reverse=True)
c.sort(reverse=True)

abc = []
for i in range(min(k, x * y)):
    for j in range(z):
        abc.append(ab[i] + c[j])


abc.sort(reverse=True)
for i in range(k):
    print(abc[i])


### FIXED CODE ###

import heapq

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

cnt = 0
q = []
arg = (0, 0, 0)
visited = {}
visited[arg] = True
heapq.heappush(q, (-(a[arg[0]] + b[arg[1]] + c[arg[2]]),) + arg)

while cnt < k:
    score, ia, ib, ic = heapq.heappop(q)
    print(-score)
    cnt += 1
    arg_a = (ia + 1, ib, ic)
    arg_b = (ia, ib + 1, ic)
    arg_c = (ia, ib, ic + 1)
    if arg_a[0] <= x - 1 and arg_a not in visited:
        heapq.heappush(
            q, (-(a[arg_a[0]] + b[arg_a[1]] + c[arg_a[2]]),) + arg_a)
        visited[arg_a] = True
    if arg_b[1] <= y - 1 and arg_b not in visited:
        heapq.heappush(
            q, (-(a[arg_b[0]] + b[arg_b[1]] + c[arg_b[2]]),) + arg_b)
        visited[arg_b] = True
    if arg_c[2] <= z - 1 and arg_c not in visited:
        heapq.heappush(
            q, (-(a[arg_c[0]] + b[arg_c[1]] + c[arg_c[2]]),) + arg_c)
        visited[arg_c] = True
### BUGGY CODE ###

from heapq import heappush, heappop
T = int(input())

for i in range(T):
    N, D = map(int, input().split())
    ans = D
    h = []
    heappush(h,D)
    for _ in range(N - 1):
        k = heappop(h)
        z = bin(k)[2:].zfill(7)
        u = map(lambda x: '0' if x == '1' else '1', z)
        t = int(''.join(u),2)
        heappush(h,t)
        ans += (127 + t - k)
    print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
T = int(input())
A = []
for i in range(T):
    N, D = map(int, input().split())
    ans = D
    h = []
    heappush(h,D)
    for _ in range(N - 1):
        k = heappop(h)
        t = 127 ^ k
        heappush(h,t)
        ans += (127 + t - k)
    A.append(ans)
for i in range(len(A)):
    print(A[i])
### BUGGY CODE ###

import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf")]*(n+1)
	d[v]=0

	Q=[]
	heapq.heappush(Q,v)

	while Q:
		u=heapq.heappop(Q)
		for i in nl[u]:
			v=i[0]
			yen=i[1]
			sunuku=i[2]
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heapq.heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

# vim: fileencoding=utf-8


def main():
    n, k = map(int, input().split())
    aList = list(map(int, input().split()))
    hyoukaList = aList[:k]
    beforeHyouka = 1
    for i in hyoukaList:
        beforeHyouka *= i

    for i in aList[k:]:
        t = hyoukaList[1:]
        t.append(i)
        hyoukaList = t

        hyouka = 1
        for i in hyoukaList:
            hyouka *= i

        if beforeHyouka < hyouka:
            print("Yes")
        else:
            print("No")
        beforeHyouka = hyouka


if __name__ == "__main__":
    main()


### FIXED CODE ###

# vim: fileencoding=utf-8


def main():
    n, k = map(int, input().split())
    aList = list(map(int, input().split()))
    hyoukaList = []
    c = 1
    for i in range(n):
        if i < k:
            continue
        b = aList[i - k]
        a = aList[i]

        if b < a:
            print("Yes")
        else:
            print("No")


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

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline
def main():
    n,k=map(int,input().split())
    a=[*map(int,input().split())]
    for _ in'_'*k:
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        a=[*accumulate(b)]
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

import math
x,y = map(int,input().split())
mod = 10**9+7

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(cmb(a+b,min(a,b))%mod)


### FIXED CODE ###

import math
x,y = map(int,input().split())
mod = 10**9+7

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0 or y>2*x or x>2*y:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(cmb(a+b,a)%mod)
### BUGGY CODE ###

h,n= map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
dp = [0]*(h+10**4)
for i in range(1,h+10**4):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(min(dp[h:]))

### FIXED CODE ###

import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from collections import defaultdict
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=defaultdict(lambda:I)
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

K = int(input())
D = int(input())
MOD = 10**9 + 7

dp = [[[0]*D for _ in range(2)] for _ in range(int(len(str(K)))+1)]
dp[0][0][0] = 1

for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        for mod_d in range(D):
            lim = 9 if smaller_flg else int(str(K)[digit])
            for digit_num in range(lim+1):
                dp[digit+1][smaller_flg or digit_num < lim][(mod_d + digit_num)%D] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][smaller_flg or digit_num < lim][(mod_d + digit_num)%D] %= MOD

print((dp[int(len(str(K)))][1][0] + dp[int(len(str(K)))][0][0] - 1) % MOD)

### FIXED CODE ###

K = int(input())
D = int(input())
MOD = 10**9 + 7

dp = [[[0]*D for _ in range(2)] for _ in range(int(len(str(K)))+1)]
dp[0][0][0] = 1

for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[digit+1][new_smaller_flg][new_mod_d] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][new_smaller_flg][new_mod_d] %= MOD

print((dp[int(len(str(K)))][1][0] + dp[int(len(str(K)))][0][0] - 1) % MOD)
### BUGGY CODE ###

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

check = 0
i = 0
while i < N-1:
    j = i + 1
    while j < N:
        if numlist[i] == numlist[j]:
            check = 1
            break
        j = j + 1
    i = i + 1

if check == 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

N = int(input())
numlist = list(map(int,input().split()))
numlist.sort()

check = 0
i = 0
while i < N-1:
    j = i + 1
    if numlist[i] == numlist[j]:
        check = 1
        break
    i = i + 1

if check == 1:
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)
upper = max(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = upper
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)
### BUGGY CODE ###

import numpy as np
N,M,Q = map(int,input().split())
vote = np.array([[0 for _ in range(N)] for _ in range(N)])
for i in range(M):
    l,r = map(int,input().split())
    vote[:l,r-1:] += 1
for i in range(Q):
    p,q = map(int,input().split())
    print(vote[p-1][q-1])

### FIXED CODE ###

N,M,Q = map(int,input().split())
vote = [[0 for _ in range(N+1)] for _ in range(N+1)]
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    vote[l][r] += 1
for i in range(1,N+1):
    for j in range(1,N+1):
        cum[i][j] = vote[i][j]+cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]
for i in range(Q):
    p,q = map(int,input().split())
    print(cum[q][q]-cum[q][p-1]-cum[p-1][q]+cum[p-1][p-1])
### BUGGY CODE ###

from collections import deque

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

MAP = [[min(i, j, N-i-1, N-j-1) for i in range(N)] for j in range(N)]

d = [[1 for i in range(N)] for j in range(N)]

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

ans = 0

for p in P:
    x = (p-1) // N
    y = (p-1) % N
    d[x][y] = 0
    
    ans += MAP[x][y]
    
    q = deque()
    
    q.append((x, y))
    
    while len(q) != 0:
        x, y = q.popleft()
        for i in range(4):
            nx = x + tx[i]
            ny = y + ty[i]
            if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] > MAP[x][y] + d[x][y]:
                MAP[nx][ny] = MAP[x][y] + d[x][y]
                q.append((nx, ny))

print(ans)

### FIXED CODE ###

from collections import deque

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

MAP = [min(i, j, N-i-1, N-j-1) for i in range(N) for j in range(N)]

d = [1] * (N ** 2)

ans = 0

def update(np, p):
    if MAP[np] > MAP[p] + d[p]:
        q.append(np)
        MAP[np] = MAP[p] + d[p]

for p in P:
    p -= 1
    
    d[p] = 0
    
    ans += MAP[p]
    
    q = deque()
    
    q.append(p)
    
    while len(q) != 0:
        p = q.popleft()
        if p % N != N-1:
            update(p+1, p)
        if p % N != 0:
            update(p-1, p)
        if p // N != N-1:
            update(p+N, p)
        if p // N != 0:
            update(p-N, p)

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

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

res = 0
if N < B:
    res = (A * N) // B
else:
    i = B - 1
    while i < N + 1:
        a = ((A * i) // B) - (A * (i // B))
        if res <= a:
            res = a
        else:
            break
        i += 1

print(res)


### FIXED CODE ###

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

res = 0
if N < B:
    res = (A * N) // B
else:
    left = B - 1
    right = 10 ** 15
    while right - left > 1:
        mid = (right + left) // 2
        a = ((A * mid) // B) - (A * (mid // B))
        if res > a:
            right = mid
        else:
            res = a
            left = mid

print(res)