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

#import numpy as np
N = int(input())
S = input()

#nums= np.zeros(N+1, dtype=int)
#for i, s in enumerate(S):
#    if s == ".":
#        nums[:i+1] += 1
#    else:
#        nums[i+1:] += 1
#
#out = nums.min()

nums = [0 for i in range(N+1)]

for i, s in enumerate(S):
    if s == ".":
        for j in range(0, i):
            nums[j] += 1
    else:
        for j in range(i+1, N+1):
            nums[j] += 1

out = min(nums)
print(out)

### FIXED CODE ###

N = int(input())
S = input()

penals1 = []
tmp1 = 0
penals2 = []
tmp2 = 0

# 半分まで準備
N_even = (N % 2 == 0)
half_N = N // 2 if N_even else (N-1) // 2 

if N == 1:
    min_val = 0
else:
    for i in range(half_N):
        if S[i] == "#":
            tmp1 += 1
        penals1.append(tmp1)

        if S[N-1-i] == ".":
            tmp2 += 1
        penals2.append(tmp2)

    if N_even:
        min_val = penals1[half_N-1] + penals2[half_N-1] 

        j = 1
        for i in range(half_N, N):
            if S[i] == "#":
                tmp1 += 1
            #penals1.append(tmp1)
            val1 = tmp1 + penals2[half_N-1-j]

            if S[N-1-i] == ".":
                tmp2 += 1
            #penals2.append(tmp2)
            val2 = penals1[half_N-1-j] + tmp2

            min_val = min(min_val, val1, val2)
            j += 1

    else:
        first = True
        j = 0

        # N = (N-1) // 2 + (N-1) // 2 + 1
        for i in range(half_N, N):
            if S[i] == "#":
                tmp1 += 1
            val1 = tmp1 + penals2[half_N-1-j]

            if S[N-1-i] == ".":
                tmp2 += 1
            val2 = penals1[half_N-1-j] + tmp2

            if first:
                min_val = min(val1, val2)
                first = False
            else:
                min_val = min(min_val, val1, val2)
            j += 1

    if S[N-1] == "#":
        tmp1 += 1
    if S[0] == ".":
        tmp2 += 1

    min_val = min(tmp1, tmp2, min_val)
print(min_val)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
#ユークリッド互除法
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b

def gcdl(l):
    if len(l) == 1:
        return l[0]
    x = l[0]
    for i in l[1:]:
        x = gcd(i,x)
    return x

can = [1]*N
for i in range(N):
    can[i] = gcdl(A[0:i]+A[i+1:])
print(max(can))

### FIXED CODE ###

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

#ユークリッド互除法
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b

L = [A[0]]
R = [A[N-1]]*N
for i in range(N-1):
    L.append(gcd(L[i], A[i+1]))
    R[N-i-2]=gcd(R[N-i-1],A[N-i-2])
can = []
for i in range(N):
    if i == 0:
        can.append(R[1])
    elif i == N-1:
        can.append(L[N-2])
    else:
        can.append(gcd(L[i-1], R[i+1]))

print(max(can))
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for i in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    newque = []
    check = [False for i in range(n)]
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]==True:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
        newque = []
    M = max(M,count)
print(n-M)

### FIXED CODE ###

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for _ in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    check = [False]*n
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        newque = []
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
    M = max(M,count)
print(n-M)
### BUGGY CODE ###

a=input().split(' ')
m=len(a)
b=0
while b<m:
    if a[b]=='0':
        print(b)
    m=m+1

### FIXED CODE ###

a=input().split(' ')
m=len(a)
b=0
while b<m:
    if a[b]=='0':
        print(b+1)
    b=b+1
### BUGGY CODE ###

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=0
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        if i*A+j*B<=F:
            for k in range(count_C+1):
                if i*A+j*B+k*C<=F:
                    for l in range(count_D+1):
                        total=i*A+j*B+k*C+l*D
                        if total!=0:
                            density=(k*C+l*D)/total
                            if total<=F and density<=E/(100+E) and max<=density:
                                max=density
                                ans[0]=total
                                ans[1]=k*C+l*D
                                if density==E/(100+E):
                                    break
print(' '.join(map(str, ans)))



### FIXED CODE ###

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=-1
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        if i*A+j*B<=F and 0<i*A+j*B:
            for k in range(count_C+1):
                if i*A+j*B+k*C<=F:
                    for l in range(count_D+1):
                        total=i*A+j*B+k*C+l*D
                        if total!=0:
                            density=(k*C+l*D)/total
                            if total<=F and density<=E/(100+E) and max<density:
                                max=density
                                ans[0]=total
                                ans[1]=k*C+l*D
                                if density==E/(100+E):
                                    print(' '.join(map(str, ans)))
                                    exit()
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import itertools
 
S = list(map(int, input().strip().split()))
N = S[0]
K = S[1]
p = list(map(int, input().strip().split()))
lists = []
for l in list(itertools.combinations(p, K)):
  sums = sum(list(l))
  lists.append(sums)

print(min(lists))

### FIXED CODE ###

S = list(map(int, input().strip().split()))
N = S[0]
K = S[1]
p = list(map(int, input().strip().split()))
lists = []
for l in range(K):
  lists.append(min(p))
  p.remove(min(p))
  
print(sum(lists))
### BUGGY CODE ###

n = int(input())
s = list(input())

ans = 999999999
for i in range(n):
    left = s[:i]
    right = s[i+1:]

    tmp_ans = 0
    for person in left:
        if person == 'W':
            tmp_ans += 1
    for person in right:
        if person == 'E':
            tmp_ans += 1
    ans = min(ans, tmp_ans)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = list(input())
num_w = 0
num_e = Counter(s[1:])['E']
ans = num_e
for i in range(1, n):
    if s[i-1] == 'W':
        num_w += 1
    if s[i] == 'E':
        num_e -= 1
    ans = min(ans, num_w + num_e)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
cb = [0] * m
for i in range(m):
    bb, cc = map(int, input().split())
    cb[i] = (cc, bb)

cb.sort(reverse=True)

arr = []
l = 0
for i in range(m):
    if l + cb[i][1] > 10**5:
        add = 10**5 - l
        for j in range(add):
            arr.append(cb[i][0])
        break
    else:
        for j in range(cb[i][1]):
            arr.append(cb[i][0])

a = a + arr
a.sort(reverse=True)
print(sum(a[0:n]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
cb = [0] * m
for i in range(m):
    bb, cc = map(int, input().split())
    cb[i] = (cc, bb)

cb.sort(reverse=True)

arr = []
l = 0
for i in range(m):
    if l + cb[i][1] > 10**5:
        add = 10**5 - l
        for j in range(add):
            arr.append(cb[i][0])
        break
    else:
        for j in range(cb[i][1]):
            arr.append(cb[i][0])
        l += cb[i][1]

a = a + arr
a.sort(reverse=True)
print(sum(a[0:n]))
### BUGGY CODE ###

N = int(raw_input())
nums = []

for i in range(N):
    nums.append(int(raw_input()))

m = -100000000000000000

for i in range(len(nums)):
    for j in range(0, i):
        if m < nums[i] - nums[j]:
            m = nums[i] - nums[j]

print(m)

### FIXED CODE ###

N = int(raw_input())
nums = []

for i in range(N):
    nums.append(int(raw_input()))

m = -1000000000000000000000000
minvalue = nums[0]

for i in range(1, len(nums)):
    minvalue = min(minvalue, nums[i-1])
    value = nums[i] - minvalue
    if m <= value:
        m = value

print(m)
### BUGGY CODE ###

iterator = [["NS", "S"], ["NT", "T"]]
var = {}
for i, j in iterator:
    var[i] = int(input())
    var[j] = [int(k) for k in input().split()]
res = 0
for T in var["T"]:
    if T in var["S"]:
        res += 1
print(res)

### FIXED CODE ###

iterator = (("NS", "S"), ("NT", "T"))
var = {}

for i, j in iterator:
    var[i] = int(input())
    var[j] = [int(k) for k in input().split()]

count = 0
for T in var["T"]:
    left = 0
    right = len(var["S"])
    while(left < right):
        mid = (left + right)//2
        if var["S"][mid] == T:
            count += 1
            break
        elif var["S"][mid] <= T:
            left = mid+1
        else:
            right = mid
print(count)
### BUGGY CODE ###

def ncr(n,r):
  if r==0 or n==r:
    return 1
  if r==1 or r==n-1:
    return n
  dp=[[0 for i in range(r+1)] for j in range(n+1)]
  a=n-r
  if r>=a:
    r=a
  
  for i in range(n+1):
    dp[i][0]=1
  dp[1][1]=1
  for i in range(2,n+1):
    for j in range(1,r+1):
      dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
  return dp[n][r]

n,k=map(int,input().split())
for i in range(1,k+1):
  ans=ncr(n-k+1,i)*ncr(k-1,i-1)
  while ans>10**9+7:
    ans%=10**9+7
  print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[[0 for i in range(k+1)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
dp[1][1]=1
for i in range(2,n+1):
  for j in range(1,k+1):
    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
for i in range(1,k+1):
  ans=dp[n-k+1][i]*dp[k-1][i-1]
  while ans>10**9+7:
    ans%=10**9+7
  print(ans)
### BUGGY CODE ###

from collections import deque
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
G = {i:[0,[-1,-1]] for i in range(N)}
for i in range(N):
    for j in range(i+1,N):
        if A[j]>=A[i] and A[j]-A[i]<=K and G[i][1][1]<0:
            G[i][1][1]=j
            G[j][0] += 1
        if A[j]<A[i] and A[i]-A[j]<=K and G[i][1][0]<0:
            G[i][1][0]=j
            G[j][0] += 1
        if G[i][1][0]>=0 and G[i][1][1]>=0:break
S = []
for i in range(N):
    if G[i][0]==0:
        S.append(i)
dist = [-1 for _ in range(N)]
for i in S:
    que = deque([(i,0)])
    dist[i] = 0
    while que:
        x,d = que.popleft()
        y = G[x][1][0]
        if y>=0 and dist[y]<d+1:
            dist[y]=d+1
            que.append((y,d+1))
        y = G[x][1][1]
        if y>=0 and dist[y]<d+1:
            dist[y]=d+1
            que.append((y,d+1))
dmax = max(dist)
print(dmax+1)

### FIXED CODE ###

from collections import deque
INFTY = 10**10
def update(i,a):
    j = i+N
    T[j] = a
    j = j//2
    while j>=1:
        T[j]=max(T[2*j],T[2*j+1])
        j = j//2
def find(l,r):
    que = deque([(1,0,N)])
    A = []
    while que:
        j,x,D = que.popleft()
        y = x+D
        if y<=l or x>=r:
            A.append(-INFTY)
        elif l<=x and y<=r:
            A.append(T[j])
        else:
            que.append((2*j,x,D//2))
            que.append((2*j+1,x+D//2,D//2))
    return max(A)
n,K = map(int,input().split())
A = [int(input()) for _ in range(n)]
k = 0
while 2**k<3*10**5:
    k += 1
N = 2**k
T = [-INFTY for _ in range(2*N)]
dp = [0 for _ in range(n)]
dp[0]=1
update(A[0],dp[0])
for i in range(1,n):
    a = A[i]
    l = max(0,a-K)
    r = min(a+K,N-1)+1
    dp[i] = max(1,find(l,r)+1)
    update(a,dp[i])
dmax = 0
for i in range(n):
    dmax = max(dmax,dp[i])
print(dmax)
### BUGGY CODE ###

import sys

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

b = []

for i in range(0,N):
	b.append(a[i])
	b.reverse()
	
for i in range(0,N):
	sys.stdout.write(str(b[i]))
	sys.stdout.write(" ")

### FIXED CODE ###

import sys

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

for i in range(0,N):
	if N-1-i*2 >= 0:
		sys.stdout.write(str(a[N-1-i*2]))
		sys.stdout.write(" ")
	elif (N % 2) == 1:
		sys.stdout.write(str(a[int((i-(N-1)/2)*2-1)]))
		sys.stdout.write(" ")
	else:
		sys.stdout.write(str(a[int((i-N/2)*2)]))
		sys.stdout.write(" ")
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0
  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i+j]-l[i]))

  return dp[n-1]

print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0
  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i+j]-l[i]))

  return dp[n-1]

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

N=int(input())
def answer(i,j):
    kotae=0
    for k in range(1,N+1):
        if int(str(k)[0])==i and int(str(k)[-1])==j:
            kotae+=1
    return kotae
answers=0
for i in range(10):
    for j in range(10):
        answers+=answer(i,j)*answer(j,i)
print(answers)


### FIXED CODE ###

N=int(input())
def answer(i,j):
    i=str(i)
    j=str(j)
    kotae=0
    for k in range(1,N+1):
        if str(k)[0]==i and str(k)[-1]==j:
            kotae+=1
    return kotae
answers=0
for i in range(1,10):
    for j in range(1,10):
        answers+=answer(i,j)*answer(j,i)
print(answers)
### BUGGY CODE ###

from operator import mul
from functools import reduce
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def com(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return (numer // denom) % MOD

for i in range(N):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * com(N - 1 - i, K - 1)
    ans = ans % MOD
    
    
print(ans % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7

ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N2 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

#print(cmb(n, r, p))
for i in range(len(A)):
  if N - 1 - i >= K - 1:
    ans += (A[- i - 1] - A[i]) * cmb(N - 1 - i, K - 1, MOD)
    ans = ans % MOD
    
    
print(ans % MOD)
### BUGGY CODE ###

import math

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

def soinsu(test):
    list_sosu = []
    x = 0
    while x==0:
        for i in range(2,test+1):
            if test % i == 0:
                test = int(test/i)
                if test == 1:
                    x = 1
                list_sosu.append(i)
                break
    return set(list_sosu)

if A == 1 or B == 1:
    print(1)
    
else:
    print(len(soinsu(A)&soinsu(B))+1)

### FIXED CODE ###

import math

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

def soinsu(test):
    list_sosu = []
    x = 0
    while x==0:
        for i in range(2,test+1):
            if i > int(math.sqrt(test)):
                list_sosu.append(test)
                x = 1
                break
            elif test % i == 0:
                test = int(test/i)
                if test == 1:
                    x = 1
                list_sosu.append(i)
                break
    return set(list_sosu)

if A == 1 or B == 1:
    print(1)
    
else:
    print(len(soinsu(A)&soinsu(B))+1)
### BUGGY CODE ###

N, W, *A = map(int, open(0).read().split())
A = zip(*[iter(A)]*2)

# dp[i][j] iまでの品物からいくつか選んで残り容量がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(A):
    for j in range(W+1):
        if j < w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)

print(max(dp[N]))

### FIXED CODE ###

N, W, *A = map(int, open(0).read().split())
A = zip(*[iter(A)]*2)

# dp[i][j] iまでの品物からいくつか選んで重さの総和がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

for i, (w, v) in enumerate(A):
    for j in range(W+1):
        if j < w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)

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

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

# 体力最小のモンスターが他全員に攻撃することを繰り返す。ただし体力0にはしない
# 全員同じ体力になったら終了

while len(set(A)) >= 2:
    A = [x%min(A) if x%min(A) != 0 else min(A) for x in A]

print(A[0])

### FIXED CODE ###

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

# 体力最小のモンスターが他全員に攻撃することを繰り返す。ただし体力0にはしない
# 全員同じ体力になったら終了

while len(set(A)) >= 2:
    A = list(set(A))
    min_A = min(A)
    A = [x%min_A if x%min_A != 0 else min_A for x in A]
    
print(A[0])
### BUGGY CODE ###

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

l=[]
la=[]
i=0
c=0
while True:
    if S[i]=="o":
        l.append(i)
        i+=C
        c+=1
    i+=1
    if c==K:
        break

i=N-1
c=0

while True:
    if S[i]=="o":
        la.append(i)
        i-=C
        c+=1
    i-=1
    if c==K:
        break
    
for i in l:
    if i in la:
        print(i+1)

### FIXED CODE ###

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

l=[0]*N
la=[0]*N
i=0
c=0
while True:
    if S[i]=="o":
        l[i]=1
        i+=C
        c+=1
    i+=1
    if i>=N:
        break

if c>K:
    exit()

i=N-1
c=0

while True:
    if S[i]=="o":
        la[i]=1
        i-=C
        c+=1
    i-=1
    if c==K:
        break
    
for i in range(N):
    if l[i]==1 and la[i]==1:
        print(i+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
p=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    p.append([xt,yt])
ans=10**20
x.sort()
y.sort()
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=p[m][0] and p[m][0]<=xmax and ymin<=p[m][1] and p[m][1]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
point=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    point.append([xt,yt])
ans=10**20
x.sort()
y.sort()
point.sort(key=lambda x:x[1])


for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            ymin=y[k]
#            ymax=y[l]
#            
            ct=0
            for p in point:
                if xmin<=p[0] and p[0]<=xmax and ymin<=p[1]:
                    ct+=1
                if ct==K:
                    A=(xmax-xmin)*(p[1]-ymin)
                    ans=min(ans,A)
                    break
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(j) for j in input().split()]
f=[int(j) for j in input().split()]
a.sort()
f.sort()
f.reverse()
if k>=sum(a):
    print(0)
    exit()

ans=[]
a.sort()
for i in range(n):
    ans.append([a[i]*f[i],a[i]])
ans.sort()
ans.reverse()

def fun(m):
    p=0
    for i,j in zip(a,f):
        if i>m//j:
            p+=i-(m//j)
            if p>k:
                return False
    return True

left=0
right=ans[0][0]
while right-left>1:
    mid=(left+right)//2
    if fun(mid):
        right=mid   #ここがleftならansもleft。
    else:
        left=mid

print(right)






### FIXED CODE ###

n,k=map(int,input().split())
a=[int(j) for j in input().split()]
f=[int(j) for j in input().split()]
a.sort()
f.sort()
f.reverse()
if k>=sum(a):
    print(0)
    exit()

ans=[]
a.sort()
for i in range(n):
    ans.append([a[i]*f[i],a[i]])
ans.sort()
ans.reverse()

def fun(m):
    p=0
    for i,j in zip(a,f):
        if i>m//j:
            p+=i-(m//j)
            if p>k:
                return False
    return True

left=0
right=ans[0][0]
while right-left>1:
    mid=(left+right)//2
    if fun(mid):
        right=mid   #ここがleftならansもleft。
    else:
        left=mid

print(right)
### BUGGY CODE ###

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

cnt = 0

for i in range(min(a)-1, max(a)+2):
    tmplist = []
    for j in a:
        tmplist.append(i-j)
        if cnt < tmplist.count(1) + tmplist.count(0) + tmplist.count(-1):
            cnt = tmplist.count(1) + tmplist.count(0) + tmplist.count(-1)

print(cnt)

### FIXED CODE ###

# 辞書を用意して最大値を取得する

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

cnt = {}

for i in a:
    for j in [-1,0,1]:
        cnt.setdefault(i+j, 0)
        cnt[i+j] += 1

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

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

cnt = 1
min = N

for i in range(1, N):
  if P[i] > min:
    continue
  for j in range(i-1, -1, -1):
    if P[i] > P[j]:
      break
  else:
    if min >P[i]:
      min = P[i]
    cnt += 1
    if min == 1:
      break
    if i < P.index(P[i]-1):
      i = P.index(P[i]-1)
      i -= 1


print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
min_p = P[0]
cnt = 0

for p in P:
  if p <= min_p:
    min_p = p
    cnt += 1

print(cnt)