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

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

inf=10**10

d=[[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split(' '))
    d[a-1][b-1]=c
    d[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                
dl=[[inf]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= L:
            dl[i][j]=1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dl[i][j] > dl[i][k] + dl[k][j]:
                dl[i][j] = dl[i][k] + dl[k][j]

q=int(input())
for _ in range(q):
    s,t = map(int,input().split(' '))
    if dl[s-1][t-1]==inf:
        print(-1)
    else:
        print(dl[s-1][t-1]-1)

### FIXED CODE ###

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

inf=10**10

d=[[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split(' '))
    d[a-1][b-1]=c
    d[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                
dl=[[inf]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= L:
            dl[i][j]=1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dl[i][j] > dl[i][k] + dl[k][j]:
                dl[i][j] = dl[i][k] + dl[k][j]

q=int(input())
for _ in range(q):
    s,t = map(int,input().split(' '))
    if dl[s-1][t-1]==inf:
        print(-1)
    else:
        print(dl[s-1][t-1]-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
warshallFloydで検索 → TLE
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d

    warshallFloyd(N+1, dp)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


if __name__ == '__main__':
    main()
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d

    warshallFloyd(N+1, dp)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


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

from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
cnt=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

stack=deque([0])
visited=[0]*n
visited[0]=1

while stack:
    cur=stack[-1]
    for i in tree[cur]:
        if visited[i]==0:
            cnt[i]+=cnt[cur]
            stack.append(i)
            visited[i]=1
            break
    else:
        stack.pop()

print(*cnt)

### FIXED CODE ###

#「探索候補スタック」「探索済みリスト」「現在地点」の３点セットでとらえる
n,q=map(int,input().split())
mat=[set() for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    mat[a-1].add(b-1)
    mat[b-1].add(a-1) # プラスした要素
count=[0]*n
for _ in range(q):
    p,score=map(int,input().split())
    count[p-1]+=score

stack=[[0,0,-1]]
while stack:
    # print(stack)
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in mat[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, m, l = map(int, input().split())
graph = [[] for i in range(N+1)]

INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c


for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

d2 = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

for i in range(N+1):
    for j in range(N+1):
        if d[i][j] <= l:
            d2[i][j] = 1

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j])

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if d2[s][t] == INF:
        print(-1)
    else:
        print(d2[s][t] - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, m, l = map(int, input().split())
graph = [[] for i in range(N+1)]

INF = 2 ** 31 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c


for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

d2 = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

for i in range(N+1):
    for j in range(N+1):
        if d[i][j] <= l:
            d2[i][j] = 1

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j])


q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if d2[s][t] == INF:
        print(-1)
    else:
        print(d2[s][t] - 1)
### BUGGY CODE ###

n = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(n):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1
ans = r*g*b
for i in range(n):
    for j in range(i+1, n):
        cur = j-i
        if j+cur <= n-1:
            if S[i] != S[j] and S[j] != S[j+cur] and S[j+cur] != S[i]:
                ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(n):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1
ans = r*g*b
for i in range(n):
    for j in range(i+1, n):
        cur = j-i
        if j+cur <= n-1:
            if S[i] != S[j] and S[j] != S[j+cur] and S[j+cur] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
a = sorted(list(set(A)),reverse = True)
B = []
for i in a:
    if A.count(i) >= 4:
        if len(B) == 0:
            print(i**2)
            exit()
        else:
            B.append(i)
            if len(B) >= 2:
                print(B[0]*B[1])
                exit()

    if A.count(i) >= 2:
        B.append(i)
        if len(B) >= 2:
            print(B[0]*B[1])
            exit()
if len(B) <= 1:
    print(0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections

n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
l = c.most_common()
L = [ l[i] for i in range(len(l)) if l[i][1] >= 2 ]
b = sorted(L,reverse = True)
if len(b) == 0:
    ans = 0
elif len(b) == 1 and b[0][1] < 4:
    ans = 0
else:
    if b[0][1] >= 4:
        ans = b[0][0]**2
    else:
        ans = b[0][0]*b[1][0]
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
s = input()
r = s.count("R")
g = s.count("G")
b = s.count("B")
num = r*g*b
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >=n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            num -=1
print(num)
### BUGGY CODE ###

N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    l = [[0] * (K+1) for _ in range(N)]
    for i in range(N):
        t = 0
        for j in range(K+1):
            if i == 0:
                if a[i] >= j:
                    l[i][j] = 1
            elif j == 0:
                t = 1
                l[i][j] = 1
            else:
                if j <= a[i]:
                    t += l[i - 1][j]
                else:
                    t += (l[i - 1][j] - l[i - 1][j - a[i] - 1])
                l[i][j] += t
    return l[-1][-1] % (10 ** 9 + 7)
            
print(main())


### FIXED CODE ###

N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())
### BUGGY CODE ###

N=int(input())
A=[int(c) for c in input().split()]
D=[0 for i in range(60)];
for a in A:
  for i in range(60):
    D[i]+=a%2
    a//=2
t=1
ans=0
for i in range(60):
  ans+=D[i]*(N-D[i])*t
  t*=2
print(ans%1000000007)

### FIXED CODE ###

N=int(input())
A=[int(c) for c in input().split()]
D=[0 for i in range(60)];
for a in A:
  for i in range(60):
    D[i]+=a%2
    a//=2
t=1
ans=0
for i in range(60):
  ans+=D[i]*(N-D[i])*t
  t*=2
print(ans%1000000007)
### BUGGY CODE ###

def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    while h:
        cnt, r, c, mode = h.popleft()
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    cost = [[H * W] * W for _ in range(H)]
    cost[0][0] = x

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    print(a.index(min(a))+1)
    a[a.index(min(a))] = 10**5+1

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
sortsecond = lambda val : val[1]
for i in range(n):
    b[i] = [i,a[i]]
b.sort(key=sortsecond)
for i in range(n):
    print(b[i][0]+1)
### BUGGY CODE ###

import sys

def main():    
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1, N+1)}
    counter = 0
    dis = [0]*(N+1)
    while False in visited.values():
        stk = [(list(visited.values()).index(False) + 1, -1, 0)]
        flag = True
        while stk:
            v, p, d = stk.pop()
            #print(v,p)
            if visited[v]:
                if dis[v]!=dis[p]+d:
                    print("No")
                    exit()
                continue
            visited[v] = True
            dis[v]=dis[p]+d
            for u,d in E[v]:
                if u != p:
                    stk.append((u,v,d))
    print("Yes")
main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    for i in range(1,N+1):
        if not visited[i]:
            stk = [( i, -1, 0)]
            while stk:
                v, p, d = stk.pop()
                #print(v,p)
                if visited[v]:
                    if dis[v]!=dis[p]+d:
                        print("No")
                        exit()
                    continue
                visited[v] = True
                dis[v]=dis[p]+d
                for u,d in E[v]:
                    if u != p:
                        stk.append((u,v,d))
    print("Yes")
main()
### BUGGY CODE ###

n, k, *p = map(int, open(0).read().split())

max_r = 0
max_i = 0
for i in range(n-k+1):
  r = sum(p[i:i+k])
  
  if r > max_r:
    max_r = r
    max_i = i
    
max_e = 0
for j in range(max_i, max_i+k):
  max_e += (p[j]+1)/2

print(max_e)

### FIXED CODE ###

n, k, *p = map(int, open(0).read().split())

q = []
for p_i in p:
  q.append((p_i+1)/2)
  
s = [0]
pre_s = 0
for q_i in q:
  pre_s += q_i
  s.append(pre_s)

ans = 0
for i in range(n-k+1):
  if ans < (s[i+k] - s[i]):
    ans = s[i+k] - s[i]
    
print(ans)
### BUGGY CODE ###

#! -*- coding: utf-8 -*-

import numpy as np
import copy

n = int(raw_input())
x = map(int,raw_input().split())

for i in range(n):
    x_i = copy.copy(x)
    del x_i[i]
    print int(np.median(x_i))


### FIXED CODE ###

#! -*- coding: utf-8 -*-

import numpy as np
import copy

n = int(raw_input())
x = map(int,raw_input().split())

x_min = copy.copy(x)
x_max = copy.copy(x)

x_min.remove(max(x))
x_max.remove(min(x))

med_x_min = int(np.median(x_min))
med_x_max = int(np.median(x_max))

if med_x_max == med_x_min:
    for i in range(n):
        print med_x_max
else:
    for i in range(n):
        if x[i] >= med_x_max:
            print med_x_min
        else:
            print med_x_max
### BUGGY CODE ###

P = [int(input()) for _ in range(6)]
N,A,B,C,D,E = P[0],P[1],P[2],P[3],P[4],P[5]
N1,N2,N3,N4,N5,goal = P[0],0,0,0,0,0
ans = 0

while goal < N:
  if N5 > 0:
    goal += min(E,N5)
    N5 -= min(E,N5)
    
  if N4 > 0:
    N5 += min(D,N4)
    N4 -= min(D,N4)
    
  if N3 > 0:
    N4 += min(C,N3)
    N3 -= min(C,N3)
    
  if N2 > 0:
    N3 += min(B,N2)
    N2 -= min(B,N2)
    
  if N1 > 0:
    N2 += min(A,N1)
    N1 -= min(A,N1)

  ans += 1

print(ans)

### FIXED CODE ###

from math import ceil
P = [int(input()) for _ in range(6)]
N,A,B,C,D,E = P[0],P[1],P[2],P[3],P[4],P[5]
N2,N3,N4,N5,N6 = ceil(N/A),ceil(N/B),ceil(N/C),ceil(N/D),ceil(N/E)

ans = max(N2,N3,N4,N5,N6) + 4
print(ans)
### BUGGY CODE ###

n = int(input())

def is_753(x):
    number = [ele for ele in str(x)]
    seven = False
    five = False
    three = False

    while '7' in number:
        seven = True
        number.remove('7')
    if not seven:
        return False

    while '5' in number:
        five = True
        number.remove('5')
    if not five:
        return False

    while '3' in number:
        three = True
        number.remove('3')
    if not three:
        return False

    if number:
        return False
    else:
        return True

count = 0

for i in range(100, n+1):
    if is_753(i):
        count+=1

print(count)

### FIXED CODE ###

n = int(input())

count = 0

def dfs(s):
    # print(s)
    # 753数ですか？
    if int(s) > n:
        return
    if all(c in s for c in "753"):
        global count
        count += 1
    for c in "753":
        dfs(s+c)


dfs('0')

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    ans = 0
    d = {}
    for i in range(n):
        t = int(s[i:])%mod
        if t in d:
            d[t] += 1
        else:
            d[t] = 1
    for k in d:
        if k != 0:
            ans += d[k]*(d[k]-1)//2
        else:
            ans += d[k]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
#ans=[0 for i in range(max(A))]
#sortA=A[:]
#sortA.sort()
dic={}
for _ in range(M):
    tmp=list(map(int,input().split()))
    try:
        dic[tmp[1]]+=tmp[0]
    except:
        dic[tmp[1]]=tmp[0]
tmp=list(dic.keys())[:]
tmp.sort()
for each in tmp:
    b_A=[i for i in A if i>=each]
    s_A=[i for i in A if i<each]
    s_A.sort()
    num=min(dic[each],len(s_A))
    for i in range(num):
        s_A[i]=each
    A=s_A+b_A
    #print(A)
print(sum(A))

### FIXED CODE ###

from collections import Counter
N,M=list(map(int,input().split()))
cards=list(map(int,input().split()))
all_c=Counter(cards)

for i in range(M):
    time,val=list(map(int,input().split()))
    try:
        all_c[val]+=time
    except:
        all_c[val]=time

tmp=list(all_c.keys())
tmp.sort(reverse=True)
total=0
sum_time=0
for i in tmp:
    if sum_time>=N:
        break
    sum_time+=all_c[i]
    if sum_time<N:
        total+=i*all_c[i]
    else:
        total+=i*(all_c[i]+N-sum_time)
print(total)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
if min(a)+1 < max(a):
    print(max([len(list(filter(lambda x: i-1 <= x and x <= i+1, a))) for i in range(min(a)+1,max(a))]))
else:
    print(len(a))

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
print(max([c[i-1]+c[i]+c[i+1] for i in set(a)]))
### BUGGY CODE ###

import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = lamp(s)
    yoko = lamp(trans(s))
    ans=0
    for hh in range(h):
        for ww in range(w):
            ans=max(ans,tate[hh][ww]+yoko[ww][hh]-1)
    print(ans)
        


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = lamp(s)
    yoko = lamp(trans(s))
    ans=0
    for hh in range(h):
        for ww in range(w):
            ans=max(ans,tate[hh][ww]+yoko[ww][hh]-1)
    print(ans)
        


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

from itertools import*
n,k=map(int,input().split())
a=10**20
for z in combinations([list(map(int,input().split()))for _ in range(n)],k):
    x=[]
    y=[]
    for i,j in z:
        x.append(i)
        y.append(j)
    a=min(a,(max(x)-min(x))*(max(y)-min(y)))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)