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


def main():
#    with open("input.txt", "r") as f:
#        t = f.readlines()
#        N = int(t[0].split()[0])
#        K = int(t[0].split()[1])
#        h = t[1].split()
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
#    print(h)
#    print(len(h))
    dp = [10**9] * max(N,K)
    dp[0] = 0

    for i in range(N):
        j = 0
        L = min(K, i)
        for j in range(L+1):
            if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
                dp[i] = dp[i-j] + abs(h[i]-h[i-j])
#        while j <= L:
#            #print(i)
#            if dp[i] > dp[i-j] + abs(h[i]-h[i-j]):
#                dp[i] = dp[i-j] + abs(h[i]-h[i-j])
#            j += 1
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

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

n=int(input())
p=list(map(int, input().split()))
c=0
for k in range(min(p), max(p)+1):
  arc = []
  abc = []
  for i in p:
    if k >= i:
      arc.append(arc)
    elif k <= i:
      abc.append(abc)
  if len(arc) == len(abc):
    c+=1
print(c)
  
      
  

### FIXED CODE ###

n=int(input())
p=sorted(list(map(int, input().split())))
print(p[int(n/2)]-p[int(n/2)-1])
### BUGGY CODE ###

MOD = 10**9 + 7


def nCr(n,r,mod):
  if n<r:
    return 0
  ret=1  
  for i in range(min(r,n-r)):
    ret = ret*(n-i)*pow(min(r,n-r)-i,mod-2,mod)%mod

  return ret%mod  

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

mi = 0
ma = 0

for i in range(1,n):
  mi += A[i-1] * nCr(n-i,k-1,MOD)
  ma += A[-i]  * nCr(n-i,k-1,MOD)  
  
print((ma - mi)%MOD)

### FIXED CODE ###

mod = 10**9 + 7

N_MAX = 10**5+1
fact = [1] * N_MAX
for i in range(1,N_MAX):
  fact[i] = (fact[i-1]*i) % mod
  
def nCr(n,r):  
  if n < r:
    return 0
  return (fact[n] * pow(fact[r]*fact[n-r] ,mod-2,mod))% mod

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

mi = 0
ma = 0

for i in range(1,n):
  m = nCr(n-i,k-1)
  mi += A[i-1] * m
  ma += A[-i]  * m
  
print((ma - mi)%mod)
### BUGGY CODE ###

from collections import deque

n, k = map(int, input().split())
a = (0,) + tuple(map(int, input().split()))

c = deque()
i = 1
while True:
    A = a[i]
    if A in c:
        break
    else:
        c.append(a[i])
        i = A

c = list(c)
s = c.index(A)

if k < s:
    print(c[k-1])
else:
    k -= s
    c = c[s:]
    ans = c[k % len(c) - 1]
    print(ans)

### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.read

def dubbling(a:np.array, k:int, MAXk=10**12) -> np.array:
    bl = MAXk.bit_length()
    b = np.empty([bl,len(a)+1], dtype=np.int64)
    b[0] = np.append(a, -1)
    for i in range(1,bl):
        x = b[i-1]
        b[i] = x[x]
    X1 = b[np.array(list(format(k,'0'+str(bl)+'b')), dtype=np.int8).astype(np.bool)[::-1]]
    ret = np.append(np.arange(len(a)), -1)
    for i in X1:
        ret = ret[i]
    return ret

n, k = map(int, input().split())
a = np.array(read().split(), dtype=np.int64)
maxk = 10**18

ans = dubbling(a-1, k, MAXk=maxk)[0] + 1
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    AA = A.copy()
    AA.remove(AA[i])
    B = set(AA)
    cnt = 0
    for num in B:
        d = AA.count(num)
        cnt += d*(d-1)//2
    print(cnt)

### FIXED CODE ###

N=int(input())
K=list(map(int, input().split()))
from collections import Counter
ans = 0
C = Counter(K)
for k, v in C.items():
    ans += v*(v-1)//2

for a in K:
    e = C[a]
    print(ans-e*(e-1)//2+(e-1)*(e-2)//2)
### BUGGY CODE ###

nw=list(map(int, input().split(" ")))
dp=[[0]*(nw[1]+1) for _ in range(nw[0]+1)]
w=[]
v=[]
i=0
ww=0
for _ in range(nw[0]):
    wv=list(map(int, input().split(" ")))
    w.append(wv[0])
    v.append(wv[1])
for i in range(nw[0]):
    for ww in range(nw[1]+1):
        if w[i] <= ww:
            dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww-w[i]]+v[i])
        dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww])
print(dp[nw[0]][nw[1]])

### FIXED CODE ###

nw=list(map(int, input().split(" ")))
dp=[[0]*(nw[1]+1) for _ in range(nw[0]+1)]
w=[]
v=[]
i=0
ww=0
for _ in range(nw[0]):
    wv=list(map(int, input().split(" ")))
    w.append(wv[0])
    v.append(wv[1])
for i in range(nw[0]):
    for ww in range(nw[1]+1):
        if w[i] <= ww:
            dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww-w[i]]+v[i])
        dp[i+1][ww]=max(dp[i+1][ww], dp[i][ww])
print(dp[nw[0]][nw[1]])
### BUGGY CODE ###

N,X,Y = (int(i) for i in input().split())


NUM = [0] * (N-1)

for i in range(1,N):
    for j in range(i+1,N+1):
        num = min(abs(i-j), abs(X-i)+1+abs(Y-j), abs(Y-i) + 1 + abs(X-j))
        if (num < N):
            NUM[num-1] += 1


for i in range(len(NUM)):
    print(NUM[i])




### FIXED CODE ###

def main():
    n, x, y = (int(i) for i in input().split())
    num_list = [0] * (n - 1)

    for i in range(1, n):
        for j in range(i + 1, n + 1):
            num = min(abs(i - j), abs(x - i) + 1 + abs(y - j), abs(y - i) + 1 + abs(x - j))
            if (num < n):
                num_list[num - 1] += 1

    for i in range(len(num_list)):
        print(num_list[i])


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

n = int(input())
a = [int(i) for i in input().split()]
ans = []
for i in range(n):
    ans = a.count(i+1)
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = [0] * (n)
for i in a:
    ans[i-1] += 1
[print(i) for i in ans]
### BUGGY CODE ###

s = input()

l = [int(s[i:]) % 2019 for i in range(len(s))]
d = {}

for i in l:
  d[i] = d.get(i, 0) + 1

count = 0  
for i in d:
  count += d[i]*(d[i]-1)//2

count += l.count(0)

print(count)

### FIXED CODE ###

import collections
s = input()

l = [int(s[-1])]
d = 10
for i in range(len(s)-2, -1, -1):
  l.append((l[-1] + int(s[i])*d) % 2019)
  d *= 10
  d %= 2019
c = collections.Counter(l)
ans = 0  
for i in c.values():
  ans += i*(i-1)//2

ans += c[0]

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

n = int(input())

res = 1

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

for i in a:
    res *= i
    
    if (res > 1000000000000000000):
        res = -1
        

if res == -1:
    for i in a:
        if a == 0:
            res = 0
            break

print(res)

### FIXED CODE ###

n = int(input())

res = 1

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

for i in a:
    res *= i
    
    if (res > 1000000000000000000):
        res = -1
        break
        

if res == -1:
    for i in a:
        if i == 0:
            res = 0
            break

print(res)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = [ni() for _ in range(n)]

s = []
for i in a:
    flag = 1
    for j in s:
        if j == i:
            s.remove(i)
            flag = 0
            break
    if flag:
        s.append(i)

print(len(s))


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
s = set()
for i in range(n):
    x = ni()
    if x in s:
        s.remove(x)
    else:
        s.add(x)
print(len(s))
### BUGGY CODE ###

S=input()
Q=int(input())
lst=[]
for _ in range(Q):
    lst.append(input().split())

#print(S, Q, lst)

str=list(S)

right=True
for operation in lst:
    if operation[0]=='1':
       right=not right

    if operation[0]=='2':
        if right==True and operation[1]=='1' or right==False and operation[1]=='2':
            str=[operation[2]]+str
        else:
            str=str+[operation[2]]

if right==True:
    print(''.join(str))
else:
    print(''.join(str[::-1]))

### FIXED CODE ###

S=input()
Q=int(input())
lst=[]
for _ in range(Q):
    lst.append(input().split())

import collections

str=list(S)
d=collections.deque(str)

right=True
for operation in lst:
    if operation[0]=='1':
       right=not right

    else:
        if right==True and operation[1]=='1' or right==False and operation[1]=='2':
            d.appendleft(operation[2])
        else:
            d.append(operation[2])
str=list(d)
if right==True:
    print(''.join(str))
else:
    print(''.join(str[::-1]))
### BUGGY CODE ###

import statistics
import copy

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    l=copy.deepcopy(a)
    l.pop(i)
    median=statistics.median(l)
    print(median)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=sorted(a)
x=l[n//2-1]
y=l[n//2]
for z in a:
    if z<=x:
        print(y)
    else:
        print(x)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    
    
def sub(u, p):
    if len(ns[u])==1 and p in ns[u]:
        return a[u]
    ub = 0
    mv = 0
    msum = 0
    for v in ns[u]:
        if p==v:
            continue
        val = sub(v, u)
        if val is None:
            return None
        mv = max(mv, val)
        msum += val
    lb = max(mv, msum//2)
    if not (lb<=a[u]<=msum):
#         print(u,lb, msum, mv)
        return None
    else:
        return a[u] - (msum-a[u])
if n==2:
    if a[0]==a[1]:
        print("YES")
    else:
        print("NO")
else:
    if len(ns[0])>1:
        ans = sub(0, -1)
    else:
        ans = sub(list(ns[0])[0], -1)

    if ans is None or ans!=0:
        print("NO")
    else:
        print("YES")

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    
    
def sub(u, p):
    if len(ns[u])==1 and p in ns[u]:
        return a[u]
    ub = 0
    mv = 0
    msum = 0
    for v in ns[u]:
        if p==v:
            continue
        val = sub(v, u)
        if val is None:
            return None
        mv = max(mv, val)
        msum += val
    lb = max(mv, msum//2)
    if not (lb<=a[u]<=msum):
#         print(u,lb, msum, mv)
        return None
    else:
        return a[u] - (msum-a[u])
if n==2:
    if a[0]==a[1]:
        print("YES")
    else:
        print("NO")
else:
    if len(ns[0])>1:
        ans = sub(0, -1)
    else:
        ans = sub(list(ns[0])[0], -1)

    if ans is None or ans!=0:
        print("NO")
    else:
        print("YES")
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,Maze,sy,sx,gy,gx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])

    return maze[gy][gx]
M=0
for (sy,sx) in pos:
  for (gy,gx) in pos:
    if bfs(h,w,S,Maze,sy,sx,gy,gx)>M:
      M=bfs(h,w,S,Maze,sy,sx,gy,gx)

print(M)     


### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,Maze,sy,sx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    m=0
    for i in range(h):
      for j in range(w):
        if maze[i][j]!=float('inf'):
          if m<maze[i][j]:
            m=maze[i][j]
            
    return m
        
M=0
for (sy,sx) in pos:
  if bfs(h,w,S,Maze,sy,sx)>M:
    M=bfs(h,w,S,Maze,sy,sx)

print(M)
### BUGGY CODE ###

from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    ans = 0
    for i in p[:s]:
        t = bisect(p[:s], lmt - i)
        ans = max(ans, i + p[t-1])
    print ans

### FIXED CODE ###

from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    print max(i + p[bisect(p, lmt - i) - 1] for i in p[:s])
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
a = [[0] * 26 for _ in range(n)] 
al = 'abcdefghijklmnopqrstuvwxyz'
cnt = 0

for i in range(n):
    for j in s[i]:
        a[i][al.index(j)] += 1 


for i in range(n-1):
    for j in range(i+1,n):
        if a[i] == a[j]:
            cnt += 1\

print(cnt)

### FIXED CODE ###

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    dic = {}
    cnt = 0

    for i in s:
        if i in dic:
            cnt+=dic[i]
            dic[i]+=1
        else:
            dic[i]=1

    print(cnt)

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

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]


jobs = [[] for _ in range(m)]
for a, b in ab:
    if a <= m:
        jobs[a - 1].append(b)

ans = 0
available = []
for job in jobs:
    available += job
    available.sort()
    if available:
        ans += available.pop()

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]


jobs = [[] for _ in range(m)]
for a, b in ab:
    if a <= m:
        jobs[a - 1].append(-b)

ans = 0
available = []
for job in jobs:
    for jo in job:
        heappush(available, jo)

    if available:
        ans -= heappop(available)

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

A,B,N=map(int,input().split())
ans=0
for i in range(1,N+1):
    if ((A*i)//B)-A*(i//B)>ans:
        ans=((A*i)//B)-A*(i//B)
print(ans)


### FIXED CODE ###

A,B,N=map(int,input().split())
ans=0
if N<B:
    for i in range(N,N+1):
        if ((A*i)//B)-A*(i//B)>ans:
            ans=((A*i)//B)-A*(i//B)
else:
    if ((A*(B-1))//B)-A*((B-1)//B)>ans:
            ans=((A*(B-1))//B)-A*((B-1)//B)
print(ans)
### BUGGY CODE ###

(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
            cGT.append(e[1])
        elif e[1] in c:
            aru = True
            c.append(e[0])
            cGT.append(e[0])
    if not aru:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
cant = list(set(p) - cGT)
res = 0
for i in cant:
    if p[i - 1] == i:
        res = res + 1

for i in cGT:
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
print(res)


### FIXED CODE ###

def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


def sameroot(x, y):
    return root(x) == root(y)


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = [[INF for _ in range(W)] for _ in range(H)]


def ok_range(h, w):
    return 0 <= h < H and 0 <= w < W


# 左上から右下へ DP してく
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 左下から右上へ
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 右上から左下
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

# 右下から左上
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

ans = 0
for c in counts:
    ans = max(ans, *c)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = np.array([list(input()) for _ in range(H)])

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))
### BUGGY CODE ###

H,W = map(int,input().split())

S = [[] for _ in range(H)]
for i in range(H):
    S[i] = list(input())

HL = [[] for _ in range(H)]
WL = [[] for _ in range(W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            HL[i].append(j)

for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            WL[j].append(i)
ma = 0
import bisect
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            ind = bisect.bisect_left(HL[i],j)
            if ind == 0:
                left = -1
            else:
                left = HL[i][ind-1]
            if ind == len(HL[i]):
                right = W
            else:
                right = HL[i][ind]
            wid_num = right-left-1

            ind_2 = bisect.bisect_left(WL[j],i)
            if ind_2 == 0:
                up = -1
            else:
                up = WL[j][ind_2-1]
            if ind_2 == len(WL[j]):
                down = H
            else:
                down = WL[j][ind_2]
            len_num = down-up-1

            ma = max(ma,wid_num+len_num-1)
print(ma)








### FIXED CODE ###

H,W = map(int,input().split())

S = [[] for _ in range(H)]
for i in range(H):
    S[i] = list(input())

HL = [[] for _ in range(H)]
WL = [[] for _ in range(W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            HL[i].append(j)

for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            WL[j].append(i)
ma = 0
import bisect
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            ind = bisect.bisect_left(HL[i],j)
            if ind == 0:
                left = -1
            else:
                left = HL[i][ind-1]
            if ind == len(HL[i]):
                right = W
            else:
                right = HL[i][ind]
            wid_num = right-left-1

            ind_2 = bisect.bisect_left(WL[j],i)
            if ind_2 == 0:
                up = -1
            else:
                up = WL[j][ind_2-1]
            if ind_2 == len(WL[j]):
                down = H
            else:
                down = WL[j][ind_2]
            len_num = down-up-1

            ma = max(ma,wid_num+len_num-1)
print(ma)
### BUGGY CODE ###

import sys
from collections import defaultdict
from copy import deepcopy

sys.setrecursionlimit(10 ** 5 + 5)

n, q = list(map(int, input().split()))
edge = defaultdict(set)
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)

tree = defaultdict(lambda: {"count": 0, "children": set()})
ROOT = 0


def rec(parent, ancestors):
    # print(parent)
    for ancestor in ancestors:
        for child in edge[parent]:
            if child in ancestors:
                continue
            tree[ancestor]["children"].add(child)
            new_ancestors = deepcopy(ancestors)
            new_ancestors.add(child)
            rec(child, new_ancestors)


rec(ROOT, set([ROOT]))

# print(tree)

opr = []
for _ in range(q):
    p, x = list(map(int, input().split()))
    p -= 1
    opr.append((p, x))

score = [0] * n
for p, x in opr:
    score[p] += x
    for child in tree[p]["children"]:
        score[child] += x

answer = " ".join(map(str, score))
print(answer)

### FIXED CODE ###

n, q = list(map(int, input().split()))
# NG: [set()] * n <- all points same set
edge = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)

opr = [0] * n
for _ in range(q):
    p, x = list(map(int, input().split()))
    p -= 1
    opr[p] += x

score = [-1] * n
q = [(0, 0)]
while q:
    # print(*q)
    node, w = q.pop()
    w += opr[node]
    score[node] = w
    # print(*score)
    for child in edge[node]:
        if score[child] == -1:
            q.append((child, w))

print(*score)
### BUGGY CODE ###

N = int(input())
HP_list = [int(i) for i in input().split()]
while len(set(HP_list))>1:
    HP_list[-1] = min([HP_list[-1]%i for i in HP_list[:-1]])
    if HP_list[-1]== 0:
        HP_list.pop(-1)
    else:
        HP_list.sort()
print(HP_list[0])

### FIXED CODE ###

import numpy as np
N = int(input())
HPs = np.array([int(i) for i in input().split()])
np.sort(HPs)
while len(HPs) > 1:
    HPs[1:] %= HPs[0]
    HPs[HPs==0] = HPs[0]
    HPs=np.unique(HPs)
print(HPs[0])