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

from sys import setrecursionlimit; setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = {}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    if x not in edge:
        edge[x] = [y]
    else:
        edge[x].append(y)
    starts -= {y}

def rec(d, e, dp):
    dp[e] = max(dp[e], d)
    if e not in edge:
        return 0
    for f in edge[e]:
        rec(d+1, f, dp)
    return max(dp)

depth = []
for s in starts:
    depth.append(rec(0, s, [0]*(N+1)))
print(max(depth))


### FIXED CODE ###

from sys import setrecursionlimit; setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = {i:[] for i in range(1, N+1)}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    starts -= {y}

memo = [-1] * (N+1)

def rec(e):
    if memo[e] != -1:
        return memo[e]
    ret = 0
    for f in edge[e]:
        ret = max(ret, rec(f) + 1)
    memo[e] = ret
    return ret

max_d = 0
for s in starts:
    max_d = max(max_d, rec(s))
print(max_d)
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 10**9+7

    Steps = [0] * (n+1)
    Steps[0] = 1
    if 1 not in As:
        Steps[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        Steps[i] = Steps[i-1] + Steps[i-2]
    ans = Steps[-1] % mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    As = set([int(input()) for _ in range(m)])
    mod = 1000000007

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        dp[i] = dp[i-1] + dp[i-2]

    ans = dp[n] % mod
    print(ans)


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

N, K = map(int,input().split())
array = []
for i in range(N):
    a,b = map(int,input().split())
    array += [a] * b
array.sort()
ans = array[K-1]
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
info.sort()
count = 0
for e in info:
    count += e[1]
    if count >= K:
        ans = e[0]
        break
print(ans)
### BUGGY CODE ###

import math

def factorial(num):
    value = 1
    if num == 0:
        return 1
    else:
        for j in range(1, num+1):
            value *= j
        return value

def main():
    n, a, b = map(int, input().split())
    sum = 0

    for i in range(1, n+1):
        if i == a or i == b:
            continue
        sum += factorial(n)/(factorial(n-i)*factorial(i))
    
    print(int(sum%(10**9+7)))

main()

### FIXED CODE ###

def comb(n, r, p):
    numer = 1
    denom = 1

    for i in range(n-r+1, n+1):
        numer = numer * i % p
    for i in range(1, r+1):
        denom = denom * i % p
    return numer * pow(denom, p-2, p)

def main():
    p = pow(10, 9) + 7
    n, a, b = map(int, input().split())
    print(((pow(2, n, p) - comb(n, a, p) - comb(n, b, p) - 1)) % p)

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

n, x, y = map(int, input().split())

for k in range(1, n):
  count = 0
  for i in range(1, n+1):
    for j in range(1, n+1):
      dist = min(abs(j-i), 1 + abs(x-i)+abs(y-j), 1 + abs(y-i)+abs(x-j))
      if dist == k:
        count+=1
  print(count//2)
    

### FIXED CODE ###

n, x, y = map(int, input().split())
dists = [0 for i in range(n+1)]

for i in range(1, n+1):
  for j in range(i+1, n+1):
    dist = min(abs(j-i), 1 + abs(x-i)+abs(y-j), 1 + abs(y-i)+abs(x-j))
    dists[dist]+=1
    
for i in range(1, n):
  print(dists[i])
### BUGGY CODE ###

import numpy as np

N = int(input())

inp = map(int,input().split(' '))

A = [int(i) for i in inp]

for i in range(N):
    B = A.copy()
    B = np.delete(B, i)
    X = np.hstack(([0],B))
    Y = np.hstack((B,[0]))
    res = np.abs(X-Y)
    print(int(np.sum(res)))


### FIXED CODE ###

import numpy as np

N = int(input())

inp = map(int,input().split(' '))

A = [0] + [int(i) for i in inp] + [0]
s = np.sum(np.abs(np.diff(A,n=1)))

for j in range(1,N+1):
    df = np.abs(A[j+1]-A[j-1]) - np.abs(A[j]-A[j-1]) - np.abs(A[j+1]-A[j])
    print(int(s+df))
### BUGGY CODE ###

from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 0
ls =list(product([0, 1], repeat=len(dic)))
ls.pop(0)

for x in ls:
    num = 1
    for z, y in zip(dic, x):
        if y == 1:
            num = dic[z]*num
            num = num%mod
    ans += num
    ans = ans%mod
print(ans)

### FIXED CODE ###

from collections import Counter
from itertools import product
 
N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 1
for x in dic:
    ans = ans*(dic[x]+1)%mod
print(ans-1)
### BUGGY CODE ###

N=int(input())
alphabet='zabcdefghijklmnopqrstuvwxyz'
result = ''
while N > 0:
  result = alphabet[N%26]+result
  if N%26==0:
    N-=1
    N//=26
print(result)

### FIXED CODE ###

N=int(input())
alphabet=list('zabcdefghijklmnopqrstuvwxyz')
result = ''
while N > 0:
  result = alphabet[N%26]+result
  if N%26==0:
    N-=1
  N//=26
print(result)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
lists=[]
emptylists=[]

for i in range(Q):
    s=int(input())
    lists.append(s)

for i ,j in enumerate(lists):
    emptylists.append([i,j])


Uselist=[K for i in range(N)]

for nums in range(Q):
    for numbers in range(N):
        if numbers==emptylists[nums][1]-1:
            
            Uselist[numbers]=Uselist[numbers]
            
        else:
            Uselist[numbers]=Uselist[numbers]-1

for num in range(N):
    if Uselist[num]>0:
        print("Yes")
    else:
        print("No")
        

### FIXED CODE ###

n,k,q=map(int,input().split())
lists=[0]*n
for i in range(q):
    a=int(input())
    lists[a-1]+=1
for i in range(n):
    check=k-(q-lists[i])
    if check>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import deque

def main():
    N, M, P = map(int, input().split())
    edge = []
    g = [[] for _ in range(N)]
    rg = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge.append((A,B,C))
        g[A].append(B)
        rg[B].append(A)
    visited = [False] * N
    rvisited = [False] * N
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        visited[v] = True
        for i in g[v]:
            if not visited[i]:
                Q.append(i)

    Q.append(N-1)
    while Q:
        v = Q.popleft()
        rvisited[v] = True
        for i in rg[v]:
            if not rvisited[i]:
                Q.append(i)
    
    OK = [False] * N
    for i in range(N):
        OK[i] = visited[i] & rvisited[i]
    
    flag = True
    d = [float('inf')] * N
    d[0] = 0
    step = 0
    while flag:
        flag = False
        for A, B, C in edge:
            if not OK[A]:
                continue
            if not OK[B]:
                continue
            newD = d[A] + C
            if newD < d[B]:
                d[B] = newD
                flag = True
        step += 1
        if step > N:
            print(-1)
            exit()

    print(max(0,-d[N-1]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    #ベルマンフォード法、N回実行してまだ更新されている場合は負の閉路が存在する
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


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

from sys import stdin, stderr
from itertools import groupby, permutations
import numpy as np


def main():
    N = int(input())
    L = np.sort(np.array([int(x) for x in input().split()]))

    ret = 0
    # print(L, file=stderr)
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            k = np.searchsorted(L, L[i] + L[j], side='right')
            if L[k - 1] == L[i] + L[j]:
                k = np.searchsorted(L, L[i] + L[j], side='left')
            # print(L[i], L[j], k, ret, file=stderr)
            ret += k - j - 1
    return ret


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

from sys import stdin, stderr
from itertools import groupby, permutations, combinations
from bisect import bisect_right
import numpy as np


def main():
    N = int(input())
    L = sorted([int(x) for x in input().split()])
    ret = 0
    # print(L, file=stderr)
    # for ij in combinations(range(N - 1), 2):
    #     i, j = ij
    #     c = L[i] + L[j] - 1
    #     k = bisect_right(L, c)
    # #     k = np.searchsorted(L, c, side='right')
    #     ret += k - j - 1

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            c = L[i] + L[j] - 1
            # k = np.searchsorted(L, c, side='right')
            k = bisect_right(L, c)
            # print(L[i], L[j], k, ret, file=stderr)
            ret += k - j - 1
    return ret


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

#Replacing
import numpy as np
N = int(input())
A = np.array(sorted(map(int, input().split())))
Q = int(input())
# u, count = np.unique(A,return_counts=True)
# asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    A = np.where(A==B,C,A)
    print(A.sum())

### FIXED CODE ###

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)
### BUGGY CODE ###

from collections import deque
from sys import exit

h,w=map(int,input().split())
sh,sw=map(lambda s: int(s)-1,input().split())
gh,gw=map(lambda s: int(s)-1,input().split())
s = [input() for _ in range(h)]
d = [[h*w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh))
while len(q):
  p = q.popleft()
  if p[0] == gw and p[1] == gh:
    print(d[gh][gw])
    exit(0)
  for dx in range(-2, 3):
    for dy in range(-2, 3):
      nx, ny = p[0] + dx, p[1] + dy
      c = 0 if abs(dx) + abs(dy) == 1 else 1
      if dx == dy == 0 or nx < 0 or ny < 0 or w <= nx or h <= ny or s[ny][nx] == '#' or d[ny][nx] <= d[p[1]][p[0]] + c:
        continue
      d[ny][nx] = d[p[1]][p[0]] + c
      np = (nx, ny)
      if c:
        q.append(np)
      else:
        q.appendleft(np)
print(-1)


### FIXED CODE ###

from collections import deque
from sys import exit

h,w=map(int,input().split())
sh,sw=map(lambda s: int(s)-1,input().split())
gh,gw=map(lambda s: int(s)-1,input().split())
s = [input() for _ in range(h)]
d = [[h*w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh, 0))
while len(q):
  p = q.popleft()
  if p[2] != d[p[1]][p[0]]:
    continue
  if p[0] == gw and p[1] == gh:
    print(d[gh][gw])
    exit(0)
  for dx in range(-2, 3):
    nx = p[0] + dx
    if nx < 0 or w <= nx:
      continue
    for dy in range(-2, 3):
      ny = p[1] + dy
      c = 0 if abs(dx) + abs(dy) == 1 else 1
      if dx == dy == 0 or ny < 0 or h <= ny or s[ny][nx] == '#' or d[ny][nx] <= d[p[1]][p[0]] + c:
        continue
      d[ny][nx] = d[p[1]][p[0]] + c
      np = (nx, ny, d[ny][nx])
      if c:
        q.append(np)
      else:
        q.appendleft(np)
print(-1)
### BUGGY CODE ###

A,B,N=map(int,input().split())
ans=0
for x in range(min(B+1,N+1)):
    a=int(A*x/B)
    b=A * int(x/B)
    ans=max(ans,a-b)

print(ans)

### FIXED CODE ###

A,B,N=map(int,input().split())
ans=0
t=min(B+1,N+1)

for x in range(t-2,t):
    a=int(A*x/B)
    b=A * int(x/B)
    ans=max(ans,a-b)

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

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e=-1):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e >0:
    col_lis.remove(edge_color[e])
  #color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      #if c==color: color+=1
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
      #color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])
### BUGGY CODE ###

N = int(input())
P = [int(x) for x in input().split()]
ans = 0
m = 0
for i in range(N):
    for j in range(m, i):
        if P[i] > P[j]:
            m = j
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
mins = [0]*N
mins[0] = P[0]
for n in range(1,N):
    mins[n] = min(P[n],mins[n-1])
ans = 0
for i in range(N):
    if P[i] == mins[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)
d = defaultdict(int)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    if d[x]:
        return d[x]
    
    if x % (bin(x).count('1')) == 0:
        d[x] = 1
        return 1

    d[x] = f(x % (bin(x).count('1'))) + 1

    return d[x]


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '1':
            tmp = O - pre
        else:
            tmp = O + pre
        ans[i] = f(tmp)
        pre *= 2

    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



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

input()
n=[int(x) for x in input().split()]
b=[]
for i in n:
    b.append(i)
    b=b[::-1]
print(" ".join([str(i) for i in b]))

### FIXED CODE ###

input()
n=[x for x in input().split()]
nb=n[::-1]
bs=n[::2]
if len(nb)%2==0:
    be=nb[::2]
else:
    be=nb[1::2]
if len(n)==1:
    print(n[0])
else:
    ans=be+bs
    if len(n)%2!=0:
        ans=ans[::-1]
    print(" ".join(ans))
### BUGGY CODE ###

n,m=map(int,input().split())
lis = []
for _ in range(n):
  lis.append(list(map(int,input().split())))
lis.sort()
ans=0
while(1):
  x,y = lis[0]
  if y >= m:
    ans += x*m
    break
  ans += x * y
  m -= y
  del(lis[0])
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
lis = []
for _ in range(n):
  lis.append(list(map(int,input().split())))
lis.sort()
ans=0
for i in range(n):
  x,y = lis[i]
  if y >= m:
    ans += x*m
    print(ans)
    quit()
  ans += x * y
  m -= y
print(ans)
### BUGGY CODE ###

N=int(input())
S_dict={}

for s_idx in range(N):
    s = input()
    
    if s not in S_dict.keys():
        S_dict.update({s:1})
    else:
        S_dict.update({s:S_dict[s]+1})
        
s_max=max(S_dict.values())

ans = []    
 
for a,b in S_dict.items():
    if b == s_max:
        ans.append(a)
    
ans.sort()
 
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
 
counter = {}
 
for i in range(N):
    temp = input()
    if temp not in counter:
        counter.update({temp : 1})
    else:
        counter.update({temp : counter[temp] + 1})
 
m = max(counter.values())
        
ans = []    
 
for a,b in counter.items():
    if b == m:
        ans.append(a)
    
ans.sort()
 
for i in ans:
    print(i)
### BUGGY CODE ###

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

K = {}
for row in A:
    if row in K:
        K[row] += 1
    else:
        K[row] = 1

# 辞書Kに関して全探索
D = {}
for row in A:
    ans = 0
    if row not in D:
        for i in K:
            tmp = K[i]
            if i == row:
                tmp = K[i]-1
            ans += tmp * ( tmp-1 ) / 2
        D[row] = int(ans)
        print(D[row])
    else:
        print(D[row])


### FIXED CODE ###

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

K = {}
for row in A:
  if row in K:
    K[row] += 1
  else:
    K[row] = 1
        
# 最大数を計算
max = 0
for i in K:
  max += int(K[i]*(K[i]-1)/2)

# 辞書Kに関して全探索
for i in A:
  print(max - int(K[i]*(K[i]-1)/2) + int((K[i]-1)*(K[i]-2)/2) )
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = []
for _ in range(Q):
    b, c = map(int, input().split())
    if b in A:
        for n in range(N):
            if A[n] == b:
                A[n] = c
    ans.append(sum(A))
    
for q in range(Q):
    print(ans[q])

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
Q = int(input())
ans = []
s = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    n = cnt[b]
    if b in cnt:
        cnt[c] += cnt[b]
        del cnt[b]
    s += (c-b)*n
    print(s)
### BUGGY CODE ###

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

def calc():
  dp = [0]*n
  for i in range(n):
    tmp = []
    for j in range(1,k+1):
      if i-j >= 0:
          tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min(tmp) if len(tmp) != 0 else 0
  return dp[n-1]

print(calc())

### FIXED CODE ###

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

def calc():
  dp = [0]*n
  for i in range(n):
    tmp = []
    for j in range(1,k+1):
      if i-j >= 0:
          tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min(tmp) if len(tmp) != 0 else 0
  return dp[n-1]

print(calc())
### BUGGY CODE ###

N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
Q = []
s = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        Q.append(P[i][1])
    else:
        s = i - 1
        break
if s >= 0:
    for j in range(s, M):
        if P[j][1] == N:
            if P[j][0] in Q:
                ans = ("POSSIBLE")
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
q = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        p = P[i][1]
        if q < 0:
            if i > 0:
                q = i - 1
            else:
                q = 0
        for j in range(q, M):
            if P[j][0] == p:
                if P[j][1] == N:
                    ans = ("POSSIBLE")
                    break
            elif P[j][0] > p:
                if q >= 0:
                    q = j - 1
                else:
                    q = 0
                break
    else:
        break
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
# 座圧
x,y=zip(*xy)
xsort=list(x)
ysort=list(y)
xsort.sort()
ysort.sort()
from bisect import bisect_left
x=[bisect_left(xsort,xi) for xi in x]
y=[bisect_left(ysort,yi) for yi in y]
xy=list(zip(x,y))
pmap=[[0]*(n) for _ in range(n)]
for x,y in xy:
  pmap[x][y]+=1
#print(pmap)
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=pmap[i][j]
    pmap[i][j]=tmp
    if i!=0:
      pmap[i][j]+=pmap[i-1][j]
def func(x1,y1,x2,y2):
  if x1==x2 or y1==y2:return 0
  if x1>x2:x1,x2=x2,x1
  if y1>y2:y1,y2=y2,y1
  if x1==0 and y1==0:
    return pmap[x2][y2]
  elif x1==0:
    return pmap[x2][y2]-pmap[x2][y1-1]
  elif y1==0:
    return pmap[x2][y2]-pmap[x1-1][y2]
  else:
    return pmap[x2][y2]-pmap[x1-1][y2]-pmap[x2][y1-1]+pmap[x1-1][y1-1]

ans=float('inf')
for x1 in range(n-1):
  for x2 in range(x1+1,n):
    for y1 in range(n-1):
      for y2 in range(1,n):
        c=func(x1,y1,x2,y2)
        if func(x1,y1,x2,y2)>=k:
          #print(xsort[x1],xsort[x2],xsort[y1],xsort[y2])
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)
#print(pmap)

### FIXED CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
# 座圧
x,y=zip(*xy)
xsort=list(x)
ysort=list(y)
xsort.sort()
ysort.sort()
from bisect import bisect_left
x=[bisect_left(xsort,xi) for xi in x]
y=[bisect_left(ysort,yi) for yi in y]
xy=list(zip(x,y))
pmap=[[0]*(n) for _ in range(n)]
for x,y in xy:
  pmap[x][y]+=1
#print(pmap)
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=pmap[i][j]
    pmap[i][j]=tmp
    if i!=0:
      pmap[i][j]+=pmap[i-1][j]
def func(x1,y1,x2,y2):
  if x1==x2 or y1==y2:return 0
  if x1>x2:x1,x2=x2,x1
  if y1>y2:y1,y2=y2,y1
  if x1==0 and y1==0:
    return pmap[x2][y2]
  elif x1==0:
    return pmap[x2][y2]-pmap[x2][y1-1]
  elif y1==0:
    return pmap[x2][y2]-pmap[x1-1][y2]
  else:
    return pmap[x2][y2]-pmap[x1-1][y2]-pmap[x2][y1-1]+pmap[x1-1][y1-1]

ans=float('inf')
for x1 in range(n-1):
  for x2 in range(x1+1,n):
    for y1 in range(n-1):
      for y2 in range(1,n):
        c=func(x1,y1,x2,y2)
        if func(x1,y1,x2,y2)>=k:
          #print(xsort[x1],xsort[x2],xsort[y1],xsort[y2])
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)
#print(pmap)