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

from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def debug(*x): stderr.write(reduce(add, repr(x)).strip("()\',") + '\n')

n, a = f()
x = f()
s = sum(x)

dp = [[[0 for i in range(n + 1)] for j in range(s + 1)] for k in range(n + 1)]
for i in range(n + 1):
    dp[i][0][0] = 1

for i in range(1, n + 1):
    for j in range(1, s + 1):
        for k in range(1, n + 1):
            dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - x[i - 1]][k - 1]

ans = 0
k = 1
while a * k <= s and k <= n:
    ans += dp[n][a*k][k]
    k += 1
print(ans)


### FIXED CODE ###

from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def debug(*x): stderr.write(reduce(add, repr(x)).strip("()\',") + '\n')

n, a = f()
x = f()
s = sum(x)

dp = [[[0 for i in range(n + 1)] for j in range(s + 1)] for k in range(n + 1)]
for i in range(n + 1):
    dp[i][0][0] = 1

for i in range(1, n + 1):
    for j in range(1, s + 1):
        for k in range(1, n + 1):
            dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - x[i - 1]][k - 1]

ans = 0
k = 1
while a * k <= s and k <= n:
    ans += dp[n][a*k][k]
    k += 1
print(ans)
### BUGGY CODE ###

def knapsack(weight,value,N,W,i,cache):
    if i == N or W <= 0:
        return 0
    if cache[i][W] != 0:
        return cache[i][W]
    op1,op2 = 0,0
    if weight[i] <= W:
        op1 = value[i] + knapsack(weight,value,N,W-weight[i],i+1,cache)
    op2 = knapsack(weight,value,N,W,i+1,cache)
    cache[i][W] = max(op1,op2)
    return cache[i][W]

N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
cache = [[0 for i in range(W+1)] for j in range(N+1)]
print(knapsack(weight,value,N,W,0,cache))

### FIXED CODE ###

N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        op1,op2 = 0,0
        if weight[i-1] <= j:
            op1 = value[i-1] + dp[i-1][j-weight[i-1]]
        op2 = dp[i-1][j]
        dp[i][j] = max(op1,op2)
print(dp[N][W])
### BUGGY CODE ###

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


for l in range(1,n):
	for r in range(l+1,n+1):
		ans += sorted(p[l-1:r])[-2]

print(ans)


### FIXED CODE ###


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

r = list(range(n))
l = list(range(n))
I = [-1] * (n+1)

for i,P in enumerate(p):
	I[P] = i
#I[1~Nまでの数字] = 0,1,...
#index を求めている
ans  = 0

for N,index in enumerate(I[1:],1):#1からスタート
	L = index -1
	if L >= 0:
		L = l[L]

	R = index + 1
	if  R < n:
		R = r[R]

	l[R-1] = L
	r[L+1] = R
#0 <= L , R < n
	if L >= 0:
		L2 = L-1
		if L2 >= 0:
			L2 = l[L2]
		ans += N * (L-L2) * (R - index)

	if R < n:
		R2 = R+1
		if R2 < n:
			R2 = r[R2]
		ans += N * (index - L ) * (R2 - R)
print(ans)
### BUGGY CODE ###

def main():
    n, m, k = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]
    B = [int(e) for e in input().split()]

    AS = [0]
    for i in range(n):
        AS.append(AS[i] + A[i])

    BS = [0]
    for i in range(m):
        BS.append(BS[i] + B[i])

    ans = 0
    for ai in range(n, -1, -1):
        if AS[ai] > k:
            continue

        bi = 0
        while AS[ai] + BS[bi] <= k:
            bi += 1
            if bi == m + 1:
                break

        ans = max(ai + bi - 1, ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m, k = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]
    B = [int(e) for e in input().split()]

    AS = [0]
    for i in range(n):
        AS.append(AS[i] + A[i])

    BS = [0]
    for i in range(m):
        BS.append(BS[i] + B[i])

    ans = 0
    bi = 0
    for ai in range(n, -1, -1):
        if bi == m + 1:
            break

        if AS[ai] > k:
            continue

        while bi < m + 1 and AS[ai] + BS[bi] <= k:
            bi += 1

        ans = max(ai + bi - 1, ans)

    print(ans)


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

R, G, B, N = map(int, input().split())
number = [R, G, B]
number = sorted(number)
M = N // number[2]
ans = 0

for i in range(0, M+1):
    value1 = i * number[2]
    L = (N-value1) // number[1]
    for j in range(0, L+1):
        value2 = j * number[1]
        if N-value1-value2 >= 0 and (N-value1-value2) % number[0] == 0:
            ans += 1
            continue

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
number = [R, G, B]
number = sorted(number)
M = N // number[2]
ans = 0

if number[2] == 1:
    print((N+2)*(N+1)//2)
else:
    for i in range(0, M+1):
        value1 = i * number[2]
        L = (N-value1) // number[1]
        for j in range(0, L+1):
            value2 = j * number[1]
            if N-value1-value2 >= 0 and (N-value1-value2) % number[0] == 0:
                ans += 1
                continue
    
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    ans = sys.maxsize
    for i in range(N):
        ans = min(ans, S[:i].count('W') + S[i + 1:].count('E'))
    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):

    W = 0
    E = S.count('E')
    ans = E + W
    for s in S:
        if s == 'E':
            E -= 1

        ans = min(E + W, ans)

        if s == 'W':
            W += 1

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


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

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)])
cnt1 = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt1[i][j] = 1

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt1[i][j] += cnt1[i][j-1]
for i in range(H):
  for j in range(W-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= W-1:
      cnt1[i][j] = max(cnt1[i][j], cnt1[i][j+1])

cnt1 = np.array(cnt1)
S = S.T
cnt2 = [[0]*H for _ in range(W)]
for i in range(W):
  for j in range(H):
    if S[i][j] == '#':
      continue
    cnt2[i][j] = 1

for i in range(W):
  for j in range(H):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt2[i][j] += cnt2[i][j-1]
for i in range(W):
  for j in range(H-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= H-1:
      cnt2[i][j] = max(cnt2[i][j], cnt2[i][j+1])
cnt2 = np.array(cnt2).T

cnt = cnt1 + cnt2
print(np.max(cnt)-1)


### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      if j == 0:
        L[i][j] = 1
      else:
        L[i][j] = L[i][j-1]+1     
      if i == 0:
        D[i][j] = 1
      else:
        D[i][j] = D[i-1][j]+1
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
  for j in range(w-1, -1, -1):
    if s[i][j] == '.':
      if j == w-1:
        R[i][j] = 1
      else:
        R[i][j] = R[i][j+1]+1

for i in range(h-1, -1, -1):
  for j in range(w):
    if s[i][j] == '.':
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

n = int(input())
s = input()
ans = 0 
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if s[i] == s[j]:
            continue
        for k in range(j+1,n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
count = 0
r = s.count('R')
g = s.count('G')
b = s.count('B')
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if j < 2*j -i <= n-1 and sorted([s[i],s[j],s[2*j-i]]) == ['B','G','R']:
            count += 1
print(r*g*b - count)
### BUGGY CODE ###

import copy

n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

for i in range(n):
    s = gcd(gcd_left[i], a[i])
    gcd_left.append(s)
    
for i in range(n):
    t = gcd(gcd_rigth[i], a[-i-1])
    gcd_rigth.append(t)

for i in range(n):
    u = copy.copy(a)
    del u[i]
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

for i in range(n):
    s = gcd(gcd_left[i], a[i])
    gcd_left.append(s)
    
for i in range(n):
    t = gcd(gcd_rigth[i], a[-i-1])
    gcd_rigth.append(t)

for i in range(n):
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))
### BUGGY CODE ###

n = int(input())

s = []
for nk in range(n):
  tmp = list(input())
  tmp.sort()
  mo = ''
  for i in tmp:
    mo += i

  s.append(mo)

s.sort()
count =0
for i in range(n):
  for j in range(i+1,n):
    if s[i] == s[j]:
      count += 1
    else:
      break
      
print(count)

### FIXED CODE ###

n = int(input())

s = []
for nk in range(n):
  tmp = list(input())
  tmp.sort()
  mo = ''
  for i in tmp:
    mo += i

  s.append(mo)

def comb(x):
  res = x*(x-1)/2
  return res
  
s.sort()
tc = 1
l = []
ans = 0

for i in range(1,n):
  if s[i-1] == s[i]:
    tc += 1

  else:
    if tc >= 2 :
      ans += comb(tc)
      tc = 1

if tc >= 2 :
  ans += comb(tc)
  tc = 1

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

from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))
Bb = [0]
tmp = 0
for i in range(N):
    tmp ^= A[i]
    Bb.append(tmp)
Bs = [0]+list(accumulate(A))
ans = 0
for l in range(1,N+1):
    for r in range(l,N+1):
        if Bb[r]^Bb[l-1] == Bs[r]-Bs[l-1]:
            ans += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))

l = 0
r = 1
tmp = A[0]
ans = 0
while l<N:
    if r==N:
        ans += r-l
        l += 1
    elif tmp+A[r] == tmp^A[r]:
        tmp = tmp+A[r]
        r += 1
    else:
        ans += r-l
        tmp = tmp-A[l]
        l += 1
print(ans)
### BUGGY CODE ###

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

latest_score = 0
before_score = 0

for cnt_k in range(k):
    if latest_score == 0:
        latest_score = a[cnt_k]
    else:
        latest_score *= a[cnt_k]

for cnt in range(1, n - k + 1):
    before_score = latest_score
    latest_score /= a[cnt-1]
    # latest_score = int(latest_score)
    latest_score *= a[cnt + k - 1]

    if before_score < latest_score:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for cnt in range(1, n - k + 1):
    if a[cnt-1] < a[cnt + k - 1]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

aaa = [int(input()) for i in range(m)]

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)
### BUGGY CODE ###

from itertools import accumulate

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

accAs = [0] + list(accumulate(As))

Bs = []
for L in range(N):
    for R in range(L, N):
        Bs.append(accAs[R + 1] - accAs[L])

ans = 0
for d in reversed(range(50)):
    num = sum([(B >> d) & 1 for B in Bs])
    if num >= K:
        ans += 1 << d
        Bs = [B if (B >> d) & 1 else 0 for B in Bs]

print(ans)


### FIXED CODE ###

from itertools import accumulate

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

accAs = [0] + list(accumulate(As))

Bs = []
for L in range(N):
    for R in range(L, N):
        Bs.append(accAs[R + 1] - accAs[L])

ans = 0
for d in reversed(range(40)):
    num = sum([(B >> d) & 1 for B in Bs])
    if num >= K:
        ans += 1 << d
        Bs = [B for B in Bs if (B >> d) & 1]

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

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def ceiler(a,b):
    return -((-a)//b)
n,k=MI()
costs=LI()
difs=LI()
costs.sort()
difs.sort(reverse=True)
lis=[0 for i in range(n)]
#print(costs)
#print(difs)
for i in range(n):
    lis[i]=costs[i]*difs[i]
#print(lis)
def judge(x):
    times=0
    for i in range(n):
        u=ceiler(lis[i]-x,difs[i])
        times+=max(0,u)
        #print(u)
    #print(x,times<=k)
    return times<=k
l,r=-1,10**13
while l+1<r:
    mid=(l+r)//2
    if judge(mid):
        r=mid
    else:
        l=mid
print(r)
    
    

    


    
 




### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def ceiler(a,b):
    return -((-a)//b)
n,k=MI()
costs=LI()
difs=LI()
costs.sort()
difs.sort(reverse=True)
lis=[0 for i in range(n)]
#print(costs)
#print(difs)
for i in range(n):
    lis[i]=costs[i]*difs[i]
#print(lis)
def judge(x):
    times=0
    for i in range(n):
        u=ceiler(lis[i]-x,difs[i])
        times+=max(0,u)
        #print(u)
    #print(x,times<=k)
    return times<=k
l,r=-1,10**13
while l+1<r:
    mid=(l+r)//2
    if judge(mid):
        r=mid
    else:
        l=mid
print(r)
### BUGGY CODE ###

import math
import bisect
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,5000)]
while top<math.sqrt(10000):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist
while(1):
    try:
        n=int(raw_input())
    except:
        break
    if n%2==0:
        if n-1 in primes:
            print 2
        else:
            print 0
    else:
        ans=0
        center=(n+1)/2
        distc=[x-center for x in primes]
        if 0 in distc:
            ans=1
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)+1
        else:
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)
        while(il>=0 and ir<len(primes)):
            if primes[ir]<n+1:
                if distc[il]+distc[ir]==0:
                    ans=ans+2
                    il=il-1
                    ir=ir+1
                elif distc[il]+distc[ir]<0:
                    ir=ir+1
                else:
                    il=il-1
        print ans

### FIXED CODE ###

import math
import bisect
primes=[2]
top=2
nlist=[2*x-1 for x in range(2,5000)]
while top<math.sqrt(10000):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist
while(1):
    try:
        n=int(raw_input())
    except:
        break
    if n%2==0:
        if n-1 in primes:
            print 2
        else:
            print 0
    else:
        ans=0
        center=(n+1)/2
        distc=[x-center for x in primes[:bisect.bisect(primes,n)]]
        if 0 in distc:
            ans=1
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)+1
        else:
            il=bisect.bisect_left(distc,0)-1
            ir=bisect.bisect_left(distc,0)
        while(il>=0 and ir<len(distc)):
            if distc[il]+distc[ir]==0:
                ans=ans+2
                il=il-1
                ir=ir+1
            elif distc[il]+distc[ir]<0:
                ir=ir+1
            else:
                il=il-1
        print ans
### 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

def lcm(a, b):
    return a * b // gcd(a, b)

c = p[0]
for x in p[1:]:
    c = lcm(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 ###

# -*- coding utf-8 -*-
import functools
import operator
 
n=int(input())
lst=list(range(1,n+1,1))
 
result = functools.reduce(operator.mul, lst)%(10**9+7)
 
print(result)


### FIXED CODE ###

# -*- coding utf-8 -*-
n=int(input())
ans=1

for i in range(1,n+1):
    ans=(ans*i)%(10**9+7)

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

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)