Problem:
 Score : 400 points    Problem Statement We have N points in a two-dimensional plane. The coordinates of the i -th point (1 \leq i \leq N) are (x_i,y_i) . Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior. Here, points on the sides of the rectangle are considered to be in the interior. Find the minimum possible area of such a rectangle.      Constraints  2 \leq K \leq N \leq 50   -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)   x_i≠x_j (1 \leq i<j \leq N)   y_i≠y_j (1 \leq i<j \leq N)   All input values are integers. (Added at 21:50 JST)         Input Input is given from Standard Input in the following format:  N  K  x_1  y_1  :  x_{N}  y_{N}       Output Print the minimum possible area of a rectangle that satisfies the condition.        Sample Input 1 4 4
1 4
3 3
6 2
8 1      Sample Output 1 21  One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1) , (8,1) , (1,4) and (8,4) . Its area is (8-1) × (4-1) = 21 .       Sample Input 2 4 2
0 0
1 1
2 2
3 3      Sample Output 2 1       Sample Input 3 4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999      Sample Output 3 3999999996000000001  Watch out for integer overflows.

Solution (Python):
n,t=map(int, input().split())
x=[]
y=[]
m=[]
for i in range(n):
    a,b=map(int, input().split())
    x.append(a)
    y.append(b)
    m.append([a,b])
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
    for j in range(i,n):
        if i>=j:continue
        for k in range(n-1):
            for l in range(k,n):
                if k>=l:continue
                count=0
                for a,b in m:
                    if x[i]<=a<=x[j] and y[k]<=b<=y[l]:
                        count+=1
                if count>=t:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Solution (Python):

from itertools import combinations

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

xl = []
yl = []
xy = []
for _ in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)
    xy.append((x,y))
yl.sort()
xy.sort(key=lambda x:x[1])

res = None
for cx in combinations(xl, 2):
    x1,x2 = cx
    if x2>x1:
        x1,x2 = x2,x1

    for y2 in yl:
        cnt = 0
        for c in xy:
            x,y = c
            if x1>=x>=x2 and y>=y2:
                cnt += 1

            if cnt==k:
                y1 = y
                s = (x1-x2)*(y1-y2)
                if res is None:
                    res = s
                else:
                    res = min(res, s)
                break

print(res)

Solution (Python):
N, K = map( int, input().split())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
SX = sorted(X)
SY = sorted(Y)
ans = 10**19
for xleft in range(N-1):
    a = SX[ xleft]
    for xright in range(xleft, N):
        b = SX[ xright]
        for yunder in range(N-1):
            c = SY[ yunder]
            for yabove in range(yunder, N):
                d = SY[ yabove]
                cnt = 0
                for i in range(N):
                    if a <= X[i] and X[i] <= b and c <= Y[i] and Y[i] <= d:
                        cnt += 1
                if cnt >= K:
                    ans = min( ans, (b-a)*(d-c))
print(ans)

Solution (Python):
N,K = map(int,input().split())
X,Y = [],[]
p = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    p.append([x,y])
X.sort(),Y.sort()
ans = abs(X[N-1]-X[0])*abs(Y[N-1]-Y[0])
for xi in range(N):
    for xj in range(xi+1,N):
        for yi in range(N):
            for yj in range(yi+1,N):
                lx,rx = X[xi],X[xj]
                dy,uy = Y[yi],Y[yj]
                num = 0
                for x,y in p:
                    if lx<=x and x<=rx and dy<=y and y<=uy:
                        num += 1
                if K==num:
                    ans = min(abs(rx-lx)*abs(uy-dy),ans)
print(ans)

Solution (Python):
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]


            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)

Solution (Python):
n, k = map(int, input().split())
s = []
for i in range(n):
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0]))
count = 0
recli = []
if k == 2:
    for i in range(n):
        for j in range(i + 1, n):
            larx = max(s[i][0], s[j][0])
            smax = min(s[i][0], s[j][0])
            lary = max(s[i][1], s[j][1])
            smay = min(s[i][1], s[j][1])
            rec = (larx - smax) * (lary - smay)
            for l in range(n):
                if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                    count += 1
            if count >= k:
                recli.append(rec)
            count = 0

elif k == 3:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                larx = max(s[i][0], s[j][0], s[p][0])
                smax = min(s[i][0], s[j][0], s[p][0])
                lary = max(s[i][1], s[j][1], s[p][1])
                smay = min(s[i][1], s[j][1], s[p][1])
                rec = (larx - smax) * (lary - smay)
                for l in range(n):
                    if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                        count += 1
                if count >= k:
                    recli.append(rec)
                count = 0
else:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                for q in range(p + 1, n):
                    larx = max(s[i][0], s[j][0], s[p][0], s[q][0])
                    smax = min(s[i][0], s[j][0], s[p][0], s[q][0])
                    lary = max(s[i][1], s[j][1], s[p][1], s[q][1])
                    smay = min(s[i][1], s[j][1], s[p][1], s[q][1])
                    rec = (larx - smax) * (lary - smay)
                    if q - i + 1 >= k:
                        if (recli == []) or (recli != [] and rec < min(recli)):
                            for l in range(i, q + 1):
                                if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                                    count += 1
                            if count >= k:
                                recli.append(rec)
                            count = 0

print(min(recli))

Solution (Python):
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

ans = (max(x) - min(x)) * (max(y) - min(y))

for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                cnt = 0

                lx = x[i]
                rx = x[j]
                uy = y[k]
                dy = y[l]

                if lx >= rx or dy >= uy:
                    continue

                for m in range(N):
                    if lx <= x[m] <= rx and dy <= y[m] <= uy:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (rx - lx) * (uy - dy))

print(ans)

Solution (Python):
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=(List_x[-1]-List_x[0])*(List_y[-1]-List_y[0])
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            if x_delta*y_delta<S:
               S=x_delta*y_delta
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(S)

Solution (Python):
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            S.append(x_delta*y_delta)
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(min(S))

Solution (Python):
n,K=map(int,input().split())
data=[]
for i in range(n):
    x,y=map(int,input().split())
    data.append((x,y))
y_sorted=sorted(data,key=lambda x:x[1])
x_sorted=sorted(data,key=lambda x:x[0])


ans=10**20
len_data=len(data)
for i in range(len_data):
    left=x_sorted[i]
    for j in range(len_data):
        down=y_sorted[j]
        if(left[1] < down[1] or down[0] < left[0]):
             continue
        for k in range(j+1,len_data):
            upp=y_sorted[k]
            if(upp[1] < left[1] or upp[0] < left[0]):
                continue
            for l in range(i+1,len_data):
                right=x_sorted[l]
                if( ans <=(right[0] - left[0]) * (upp[1] -down[1])):
                    break
                if((right[0] - left[0]) * (upp[1] -down[1])==0):
                    continue
                if(right[1] < down[1] or right[1] > upp[1] \
                 or right[0] < down[0] or right[0] < upp[0]):
                    continue
                tmp=0
                for m in range(len_data):
                    now=x_sorted[m]
                    if(down[1] <= now[1] <= upp[1] and left[0] <= now[0] <= right[0]):
                        tmp+=1
                        if(tmp==K):
                            ans= min( [ans, (right[0] - left[0]) * (upp[1] -down[1])])
                            break




print(ans)

Solution (Python):
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        for l in range(N):
            for m in range(l+1, N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N, K = inpl()
inf = 10**19+1
x = [inf for _ in range(N+1)]
y = [inf for _ in range(N+1)]
H = defaultdict(lambda: 0)

for i in range(N):
    x[i], y[i] = inpl()
    H[(x[i],y[i])] = 1
    

x.sort()
y.sort()

for i in range(N-1):
    for j in range(N):
        H[(x[i+1],y[j])] = H[(x[i],y[j])] + H[(x[i+1],y[j])]

for j in range(N-1):
    for i in range(N):
        H[(x[i],y[j+1])] = H[(x[i],y[j])] + H[(x[i],y[j+1])]

for i in range(N+1):
    H[(x[i],inf)] = H[(inf,y[i])] = 0
H[(inf,inf)] = 0

ans = inf
for i in range(N):
    for j in range(N):
        for t in range(i):
            if i-t+1 < K:
                break
            for s in range(j):
                if j-s+1 < K:
                    break
                if H[(x[i],y[j])] - H[(x[t-1],y[j])] -\
                H[(x[i],y[s-1])] + H[(x[t-1],y[s-1])] != K:
                    continue
                ans = min(ans,(x[i]-x[t])*(y[j]-y[s]))
print(ans)

Solution (Python):
n, k = map(int, input().split())

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]




a = 0
b = 1
ans = sx[n - 1] * sy[n - 1]
temp = 0
for p in range(n):
    for q in range(p + 1, n):
        for a in range(n):
            for b in range(a + 1, n):
                count = 0
                if d[b + 1][q + 1] - d[b + 1][p] - d[a][q + 1] + d[a][p] >= k:
                    ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

Solution (Python):
from itertools import accumulate
import numpy as np
N,K=list(map(int,input().split()))
point=[]
x_set=set()
y_set=set()

for i in range(N):
    x,y=list(map(int,input().split()))
    point.append((x,y))
    x_set.add(x)
    y_set.add(y)
x_arr=sorted(list(x_set))
y_arr=sorted(list(y_set))

x_dic={}
y_dic={}
for i,x in enumerate(x_arr):
    x_dic[x]=i
for i,y in enumerate(y_arr):
    y_dic[y]=i

square=[[0 for _ in range(len(x_arr)+1)] for _ in range(len(y_arr)+1)]
for p in point:
    j=x_dic[p[0]]
    i=y_dic[p[1]]
    square[i+1][j+1]+=1
square=np.array(square)

for i,line in enumerate(square):
    square[i]=list(accumulate(line))
for i,row in enumerate(square.T):
    square[:,i]=list(accumulate(row))

h=1
ans=float('inf')
W=len(square[0])
H=len(square)
for i in range(1,H):
    for j in range(i,H):
        h=1
        for k in range(1,W): 
            num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
            while num>=K:
                S=max(y_arr[j-1]-y_arr[i-1],1)*max(x_arr[k-1]-x_arr[h-1],1)
                ans=min(ans,S)
                h+=1
                num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
print(int(ans))

Solution (Python):
N,K = map(int,input().split())
z = [0]*N
for i in range(N):
    x,y = map(int,input().split())
    z[i] = (x,y)
z.sort(key=lambda x:x[1])
H = z[N-1][1]-z[0][1]
z.sort()
W = z[N-1][0]-z[0][0]
ans = H*W
for i in range(N-K+1):
    for j in range(i+K-1,N):
        z_ = z[i:j+1].copy()
        W = z_[-1][0]-z_[0][0]
        z_.sort(key=lambda x:x[1])
        for k in range(len(z_)-K+1):
            H = z_[k+K-1][1]-z_[k][1]
            if H*W < ans:
                ans = H*W
print(ans)

Solution (Python):
N, K = map(int, input().split())
X, Y = [], []
D = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    D.append((x, y))

X = sorted(X)
Y = sorted(Y)
num = float("inf")
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                tmp = 0
                for m in range(N):
                    if X[i] <= D[m][0] <= X[j] and Y[k] <= D[m][1] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)

Solution (Python):
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
x=[t[0] for t in xy]
y=[t[1] for t in xy]

res=[]
for i in range(n-1):
    for j in range(i+1,n):
        for a in range(n-1):
            for b in range(a+1,n):
                l=min(x[i],x[j])
                r=max(x[i],x[j])
                d=min(y[a],y[b])
                u=max(y[a],y[b])
                tk=0
                for t in xy:
                    if l<=t[0]<=r and d<=t[1]<=u:
                        tk+=1
                if tk>=k:
                    res.append((r-l)*(u-d))
print(min(res))

Solution (Python):
N, K = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(N)]
x = sorted(list(zip(*p))[0])
y = sorted(list(zip(*p))[1])
dic_x = {v: i + 1 for i, v in enumerate(x)}
dic_y = {v: i + 1 for i, v in enumerate(y)}
cum_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i, j in p:
    cum_sum[dic_y[j]][dic_x[i]] = 1

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[i][j + 1] += cum_sum[i][j]

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[j + 1][i] += cum_sum[j][i]

ans = 10 ** 20
for l in range(N):
    for r in range(l + 1, N):
        for d in range(N):
            for u in range(d + 1, N):
                z = cum_sum[u + 1][r + 1] - cum_sum[d][r + 1] \
                     - cum_sum[u + 1][l] + cum_sum[d][l]
                if z >= K:
                    ans = min(ans, (x[r] - x[l]) * (y[u] - y[d]))
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,k = li()
xs = []
ys = []
points = []
for _ in range(n):
    x,y = li()
    xs.append(x)
    ys.append(y)
    points.append((x,y))
    
xs.sort()
ys.sort()

rank_x = {}
rank_y = {}
for i, x in enumerate(xs):
    rank_x.update({x:i+1})
for i, y in enumerate(ys):
    rank_y.update({y:i+1})

field = [[0 for _ in range(n+1)] for _ in range(n+1)]
for px,py in points:
    field[rank_y[py]][rank_x[px]] = 1
    
for row in range(n+1):
    field[row] = list(accumulate(field[row]))
    
for col in range(n+1):
    for row in range(n):
        field[row+1][col] += field[row][col]

ans = float("inf")
for xst in range(n):
    for xed in range(xst+1,n):
        for yst in range(n):
            for yed in range(yst+1,n):
                if field[yed+1][xed+1] + field[yst][xst] \
                    -field[yed+1][xst] - field[yst][xed+1]>= k:
                    ans = min(ans, (xs[xed]-xs[xst])*(ys[yed]-ys[yst]))

print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
xs = []
ys = []
points = []
for _ in range(n):
    x,y = li()
    xs.append(x)
    ys.append(y)
    points.append((x,y))
    
xs.sort()
ys.sort()

ans = float("inf")
for xst in range(n):
    for xed in range(xst+1,n):
        for yst in range(n):
            for yed in range(yst+1, n):
                cnt = 0
                for px,py in points:
                    if xs[xst] <= px <= xs[xed] and ys[yst] <= py <= ys[yed]:
                        cnt += 1
                        
                if cnt >= k:
                    ans = min(ans, (xs[xed]-xs[xst])*(ys[yed]-ys[yst]))
                    
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
x = []
y = []
points = [tuple(li()) for _ in range(n)]
for i in range(n):
    x.append(points[i][0])
    y.append(points[i][1])
    
x.sort()
y.sort()

ans = (x[-1]-x[0]) * (y[-1]-y[0])
for u,xs in enumerate(x[:-1]):
    for xt in x[u+1:]:
        for v,ys in enumerate(y[:-1]):
            for yt in y[v+1:]:
                area = (xt-xs) * (yt-ys)
                inner = 0
                for xi,yi in points:
                    if xs<=xi<=xt and ys<=yi<=yt:
                        inner += 1
                        
                if inner >= k:
                    ans = min(ans,area)
                    
                    
print(ans)

Solution (Python):
from itertools import product

N, K = map(int, input().split())
x, y = [None] * N, [None] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

xary = sorted(x)
yary = sorted(y)

ans = float('inf')
for i, j, k, l in product(range(N), repeat=4):
    if i >= j or k >= l:
        continue
    x1, x2 = xary[i], xary[j]
    y1, y2 = yary[k], yary[l]
    cnt = 0
    for xx, yy in zip(x, y):
        if x1 <= xx <= x2 and y1 <= yy <= y2:
            cnt += 1
    if cnt >= K:
        s = abs(x1 - x2) * abs(y1 - y2)
        ans = min(ans, s)
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)

ans = INF
xx = sorted(list(xx))
Lx = len(xx)
xys.sort(key = lambda x: x[1])
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        yy = []
        for x,y in xys:
            if x1 <= x <= x2:
                yy.append(y)
        Ly = len(yy)
        if Ly < K:
            continue
        else:
            for l in range(Ly-K+1):
                r = l+K-1
                ans = min((yy[r]-yy[l])*(x2-x1),ans)

print(ans)

Solution (Python):
N, K = map(int, input().split())
xy = [[int(x) for x in input().split()] for _ in range(N)]

xs, ys = tuple(zip(*xy))
cmpx = sorted(xs)
cmpy = sorted(ys)

x2cmp = dict((x, i) for i,x in enumerate(cmpx))
y2cmp = dict((x, i) for i,x in enumerate(cmpy))

sm = [[0] * (N + 1) for _ in range(N + 1)]
for x, y in xy:
    sm[x2cmp[x]][y2cmp[y]] = 1

for i in range(N):
    for j in range(N):
        sm[i][j] += sm[i][j - 1]
for j in range(N):
    for i in range(N):
        sm[i][j] += sm[i - 1][j]

ans = float('inf')
for x1 in range(N):
    for y1 in range(N):
        for x2 in range(x1 + 1, N):
            for y2 in range(y1 + 1, N):
                k = sm[x2][y2] - sm[x2][y1 - 1] - sm[x1 - 1][y2] + sm[x1 - 1][y1 - 1]
                if k == K:
                    area = (cmpx[x2] - cmpx[x1]) * (cmpy[y2] - cmpy[y1])
                    ans = min(ans, area)

print(ans)

Solution (Python):
n, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(n)]

xy = sorted(xy)
ans = 4*10**18
for i in range(n-k+1):
    x_left = xy[i][0]
    for j in range(i+k-1, n):
        x_right = xy[j][0]
        y_mid = sorted([y for x, y in xy[i:j+1]])
        for k_ in range(len(y_mid)-k+1):
            y_bottom = y_mid[k_]
            y_top = y_mid[k_+k-1]
            ans = min(ans, (x_right-x_left)*(y_top-y_bottom))
print(ans)

Solution (Python):
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
sx = sorted(xy)
nx = list(enumerate(sx))

ans = float('inf')
for i,[x1,y1] in nx:
    for j,[x2,y2]in nx:
        if i>j:
            continue
        sy = sorted(y for x,y in sx[i:j+1])
        for l in range(len(sy)-k+1):
            y3,y4 = sy[l],sy[l+k-1]
            if y3<=y1<=y4 and y3<=y2<=y4:
                ans = min(ans, (x2-x1)*(y4-y3))
print(ans)

Solution (Python):
from itertools import combinations
n, k = map(int, input().split())
dots = sorted([list(map(int, input().split())) for _ in range(n)])

ans = float("inf")
for x1, x2 in combinations(range(n), 2):
	wid = dots[x2][0] - dots[x1][0]
	dots_cand = sorted(dots[x1: x2 + 1], key=lambda x: x[1])
	for y1, y2 in combinations(range(x2 + 1 - x1), 2):
		if y2 - y1 + 1 >= k:
			area = (dots_cand[y2][1] - dots_cand[y1][1]) * wid
			if area < ans:
				ans = area

print(ans)

Solution (Python):
from itertools import combinations
n, k = map(int, input().split())
dots = sorted([list(map(int, input().split())) for _ in range(n)])

ans = float("inf")
for x1, x2 in combinations(range(n), 2):
	wid = dots[x2][0] - dots[x1][0]
	dots_cand = sorted(dots[x1: x2 + 1], key=lambda x: x[1])
	for y1, y2 in combinations(range(x2 + 1 - x1), 2):
		if y2 - y1 + 1 >= k:
			area = (dots_cand[y2][1] - dots_cand[y1][1]) * wid
			if area < ans:
				ans = area

print(ans)

Solution (Python):
n, k = map(int, input().split())
pos = []
for i in range(n):
    x, y = map(int, input().split())
    pos.append((x, y))

pos.sort()
minSq = 4000000000000000000

for l in range(n):
    lx, ly = pos[l]
    que = []
    for r in range(l, n):
        rx, ry = pos[r]
        que.append(ry)
        sizes = sorted(que)
        n_sizes = len(que)
        if n_sizes < k:
            continue
        for i_top in range(k - 1, n_sizes):
            top = sizes[i_top]
            bottom = sizes[i_top - k + 1]
            minSq = min(minSq, (top - bottom) * (rx - lx))

print(minSq)

Solution (Python):
from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

Solution (Python):
N,K=map(int,input().split())

L = []
for i in range(N):
    li = list(map(int,input().split()))
    L.append(li)
    


L.sort()



ans=10**37
for i in range(N):
    for j in range(i+1,N):
        t=L[j][0]-L[i][0]
        S=sorted(x[1] for x in L[i:j+1])
        for k in range(len(S)-K+1):
            u=S[K+k-1]-S[k]
            ans=min(ans,u*t)
print(ans)

Solution (Python):
N,K=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
L.sort()
ans=10**37
for i in range(N):
    for j in range(i+1,N):
        t=L[j][0]-L[i][0]
        S=sorted(x[1] for x in L[i:j+1])
        for k in range(len(S)-K+1):
            u=S[K+k-1]-S[k]
            ans=min(ans,u*t)
print(ans)

Solution (Python):
import itertools
n,k = map(int,input().split())
x = []
a = []
b = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
    a.append(x1)
    b.append(y1)
ue = list(itertools.combinations(a,2))
mi = list(itertools.combinations(b,2))
e = len(ue)
ue.extend(mi)
ans = float("inf")
for i in range(e):
  u = ue[i]
  if u[0] > u[1]:
    UP = u[0]
    DO = u[1]
  else:
    UP = u[1]
    DO = u[0]
  for j in range(e):
    kazu = 0
    m = ue[j+e]
    if m[0] > m[1]:
      RI = m[0]
      LE = m[1]
    else:
      RI = m[1]
      LE = m[0]
    for i in  x:
      c = i[0]
      d = i[1]
      if (UP >= c and c>= DO and RI >= d and d >= LE):
        kazu += 1
    if kazu >= k:
      ans = min(ans,(UP-DO)*(RI-LE))
print(ans)

Solution (Python):
from itertools import product,combinations
N,K=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
ans=10**37
def f(i,j,k,l):
    n=0
    s=min(L[j][0],L[i][0])
    t=max(L[j][0],L[i][0])
    u=min(L[k][1],L[l][1])
    w=max(L[k][1],L[l][1])
    for e in L:
        if s<=e[0]<=t and u<=e[1]<=w:
            n+=1
    if n>=K:
        return (t-s)*(w-u)
    return 10**37
for i,j in combinations(range(N),2):
    for k,l in combinations(range(N),2):
        
        ans=min(ans,f(i,j,k,l))
print(ans)

Solution (Python):
N,K=map(int,input().split())
p = sorted([[int(_) for _ in input().split()] for i in range(N)])
a=10**20
for xi in range(N-K+1):
  for xj in range(xi+K-1,N):
    q = sorted(y for x,y in p[xi:xj+1])
    for yi,yj in zip(q,q[K-1:]):
      if yi<=p[xi][1] and p[xj][1]<=yj:
        a = min(a, (p[xi][0]-p[xj][0])*(yi-yj))
print(a)

Solution (Python):
N,K=map(int,input().split())
p = sorted([[int(_) for _ in input().split()] for i in range(N)])
a=10**20
for xi in range(N-K+1):
  for xj in range(xi+K-1,N):
    q = sorted(y for x,y in p[xi:xj+1])
    for yi in range(xj-(xi+K-1)+1):
      yj = yi+K-1 
      if q[yi]<=p[xi][1] and p[xj][1]<=q[yj]:
        a = min(a, (p[xi][0]-p[xj][0])*(q[yi]-q[yj]))
print(a)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


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, K, XY):
    X = sorted(map(lambda x: x[0], XY))
    RX = X[::-1]
    Y = sorted(map(lambda x: x[1], XY))
    RY = Y[::-1]

    ans = sys.maxsize
    for lx in X:
        for rx in RX:
            if lx > rx:
                break
            for by in Y:
                for ty in RY:
                    if by > ty:
                        break

                    k = 0
                    for x, y in XY:
                        if lx <= x <= rx and by <= y <= ty:
                            k += 1
                    if k >= K:
                        ans = min(ans, (rx-lx)*(ty-by))
                    else:
                        break

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, K, XY))


if __name__ == '__main__':
    main()