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

h,w = map(int,input().split())
#0が進めるところ、1は無理
lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]
#ゴールは9
lis[h-1][w-1] = 9
#print(lis)
#[[0, 0, 1], [1, 0, 0], [0, 0, 9]]

#この問題ではbfsを始める前に、もともと壁だったところの数を記録しておく
road = 0
for row in lis:
    for column in row:
        if column != 1:
            road +=1

count = 0
#(開始x,開始y,移動回数)
pos = [[0,0,0]]
while len(pos)>0:
    x,y,depth = pos.pop(0)

    if lis[x][y] == 9:
        count = depth
        break

    #探索済みのところは、1にする
    lis[x][y] = 1

    #遷移先は0or9なので、1以外なら行ける
    if x-1>=0 and lis[x-1][y] != 1:
        pos.append([x-1,y,depth+1])
    if x+1<h and lis[x+1][y] != 1:
        pos.append([x+1,y,depth+1])
    if y-1>=0 and lis[x][y-1] != 1:
        pos.append([x,y-1,depth+1])
    if y+1<w and lis[x][y+1] != 1:
        pos.append([x,y+1,depth+1])

#(全マス) - (壁) - (移動する道順上のマスの数 ＝ 最短の移動回数＋１）
if count == 0:
    print(-1)
else:
    print(road-(count+1))

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
count = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        temp = (N - i * R - j * G)/B
        if temp >= 0 and temp - int(temp) == 0:
            count += 1
print(count)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
count = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        temp = (N - i * R - j * G)/B
        if temp >= 0 and temp - int(temp) == 0:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np
n,k = input().split()
n = int(n)
k = int(k)
l = list()
for i in range(n):
    a, b = input().split()
    for j in range(int(b)):
        l.append(int(a))

l.sort()
print(l[k-1])
    

### FIXED CODE ###

N, K = map(int,input().split())
# a_list = []
b_dict = {}

for i in range(N):
    a, b = map(int,input().split())
    if a in b_dict:
        b_dict[a] += b
    else:
        b_dict[a] = b
        
a_list = list(b_dict.keys())
a_list.sort()


for a in a_list:
    K -= b_dict[a]
    if K <= 0:
        break

print(a)
### BUGGY CODE ###

S=input()
A=0 #Aの数
B=0 #ABの数
C=0 #ABCの数
n=1 #通り数
mod=10**9+7
for s in S:
    if s=="?":
        C=3*C+B
        B=3*B+A
        A=3*A+n
        n*=3
    elif s=="A":
        A+=n
    elif s=="B":
        B+=A
    else:
        C+=B
    A%=mod
    B%=mod
    C%=mod
print(C)

### FIXED CODE ###

S=input()
A=0 #Aの数
B=0 #ABの数
C=0 #ABCの数
n=1 #通り数
mod=10**9+7
for s in S:
    if s=="?":
        C=3*C+B
        B=3*B+A
        A=3*A+n
        n*=3
    elif s=="A":
        A+=n
    elif s=="B":
        B+=A
    else:
        C+=B
    A%=mod
    B%=mod
    C%=mod
    n%=mod
print(C)
### BUGGY CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime
prime = primelist(1001)

def factorization(n):
    arr = []
    temp = n
    for i in prime:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

fact = [0] * (1000001)
pri = []
for i in range(n):
    f = factorization(a[i])
    for fac, c in f:
        fact[fac] = max(fact[fac], c)

fact_list = []
for i in range(1000001):
    if fact[i] > 0:
        fact_list.append((i, fact[i]))




ans = 0
for i in range(n):
    m = modinv(a[i])
    for fac, c in fact_list:
        m *= pow(fac, c, mod)
        m %= mod

    ans += m
    ans %= mod

print(ans)


### FIXED CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = 1.0e+9 + 7
rest = 0
for i in range(N-1):
  for j in range(N-i-1):
    rest +=(A[i]*A[i+j+1])%mod_num

print(int(rest%mod_num))

### FIXED CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = int(1.0e+9 + 7)
rest = 0
temp = 0

for i in range(N-1):
  temp+=A[i]
  rest += temp*A[i+1]
  rest = rest%mod_num

print(int(rest%mod_num))
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N)] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
Q,K = map(int,input().split())
cost = dijkstra(edge,False,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))

### FIXED CODE ###

N = int(input())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1].append((c,b-1))
    graph[b-1].append((c,a-1))
Q,K = map(int,input().split())

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

cost = dijkstra(graph,N,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))
### BUGGY CODE ###

import math
from itertools import product
b=list(map(int,input().split(" ")))
c=2*b[0]/b[1]
a=[i for i in range(1,int(c)+1)]
a=list(product(a,repeat=3))
t=0
for i in a:
    if (i[0]+i[1]-i[2])*b[1]/2.0>=1 and (i[0]+i[1]-i[2])*b[1]/2.0<=b[0] and math.modf((i[0]+i[1]-i[2])*b[1]/2.0)[0]==0:
        if (i[0]+i[2]-i[1])*b[1]/2.0>=1 and (i[0]+i[2]-i[1])*b[1]/2.0<=b[0] and math.modf((i[0]+i[2]-i[1])*b[1]/2.0)[0]==0:
            if (i[2]+i[1]-i[0])*b[1]/2.0>=1 and (i[2]+i[1]-i[0])*b[1]/2.0<=b[0] and math.modf((i[2]+i[1]-i[0])*b[1]/2.0)[0]==0:
                t+=1
print (t)


### FIXED CODE ###

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

ans = 0
for a in range(1, N+1):
    if(2 * a % K == 0):
        beg = K - a % K
        end = N
        cnt = (end - beg + K) // K
        ans += cnt * cnt

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

s = input().strip()
K = int(input())
C = {}
for i in range(len(s)):
    if s[i] not in C:
        C[s[i]] = []
    C[s[i]].append(i)
D = {}
for a in C:
    for i in C[a]:
        x = s[i]
        if x not in D:
            D[x] = 0
        D[x] += 1
        for j in range(i+1,len(s)):
            x += s[j]
            if x not in D:
                D[x] = 0
            D[x] += 1
D = sorted(list(D.keys()))
print(D[K-1])

### FIXED CODE ###

S = input().strip()
N = len(S)
K = int(input())
A = []
for k in range(1,min(6,N+1)):
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in A:
            A.append(x)
A = sorted(A)
print(A[K-1])
### BUGGY CODE ###

N,K = map(int,input().split())
As = list(map(int,input().split()))
route = [0]
pre = 0
i = 0
for k in range(K):
    i = As[i]-1
    if i in route:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
#print(route)
mod = len(route)
print(route[(K-pre)%mod]+1)

### FIXED CODE ###

N,K = map(int,input().split())
As = list(map(int,input().split()))
towns = [0]*N
route = [0]
pre = 0
i = 0
towns[0] = 1
for _ in range(K):
    i = As[i]-1
    if towns[i]>0:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
    towns[i] = 1
mod = len(route)
print(route[(K-pre)%mod]+1)
### BUGGY CODE ###

N, X, Y = map(int,input().split())
X -= 1
Y -= 1

nallpath = N*(N-1)//2
distance = [0] * nallpath

indx = 0
for j in range(N-1):
    for i in range(j+1,N):
        if i <= X:
            distance[indx] = i - j
        elif j >= Y:
            distance[indx] = i - j
        elif j <= X and Y<= i:
            distance[indx] = i - j - (Y-X-1)
        elif  X <= j < i <= Y:
            distance[indx] = min(i-j, (j-X)+(Y-i)+1)
        elif j <= X and X < i <= Y:
            distance[indx] = (X-j) + min(i-X, Y-i+1)
        else:
            distance[indx] = (i-Y) + min(Y-j, j-X+1)
        indx += 1
for i in range(N-1):print(distance.count(i+1))


### FIXED CODE ###

N, X, Y = map(int,input().split())
X -= 1
Y -= 1

npath = [0] * (N-1)

indx = 0
for j in range(N-1):
    for i in range(j+1,N):
        if i <= X:
            distance = i - j
        elif j >= Y:
            distance = i - j
        elif j <= X and Y<= i:
            distance = i - j - (Y-X-1)
        elif  X <= j < i <= Y:
            distance = min(i-j, (j-X)+(Y-i)+1)
        elif j <= X and X < i <= Y:
            distance = (X-j) + min(i-X, Y-i+1)
        else:
            distance = (i-Y) + min(Y-j, j-X+1)
        npath[distance-1] +=1
for i in range(N-1):print(npath[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, K: int, h: "List[int]"):
    dp = [float('inf')] * N
    dp[0] = 0

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, K, h)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, K: int, h: "List[int]"):
    dp = [float('inf')] * N
    dp[0] = 0

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, K, h)
    print(result)

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

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

X = sum(a)
x = list(sum(a[:i+1]) for i in range(n))
ans = min(list(abs(X-2*x[i]) for i in range(n-1)))

print(ans)

### FIXED CODE ###

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

X = sum(a)
x =[a[0]]
for i in range(n-1):
	x.append(x[i]+a[i+1])
ans = min(list(abs(X-2*x[i]) for i in range(n-1)))

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

a, b, c, d = map(int, input().split())
MOD = 998244353

dp = [[0] * (d + 1) for _ in range(c + 1)]
dp[a][b] = 1

for i in range(a + 1, c + 1):
    dp[i][b] = dp[i - 1][b] * b % MOD

for j in range(b + 1, d + 1):
    dp[a][j] = dp[a][j - 1] * a % MOD

for i in range(a + 1, c + 1):
    for j in range(b + 1, d + 1):
        dp[i][j] = (dp[i][j - 1] * i + dp[i - 1][j] * j - dp[i - 1][j - 1] * (i - 1) * (j - 1)) % MOD

print(dp[c][d])


### FIXED CODE ###

a, b, c, d = map(int, input().split())
MOD = 998244353

dp = [[0] * (d + 1) for _ in range(c + 1)]
dp[a][b] = 1

for i in range(a + 1, c + 1):
    dp[i][b] = dp[i - 1][b] * b % MOD

for j in range(b + 1, d + 1):
    dp[a][j] = dp[a][j - 1] * a % MOD

for i in range(a + 1, c + 1):
    for j in range(b + 1, d + 1):
        dp[i][j] = (dp[i][j - 1] * i + dp[i - 1][j] * j - dp[i - 1][j - 1] * (i - 1) * (j - 1)) % MOD

print(dp[c][d])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split(" ")))
#n=6
#a=[1,3,-4,2,2,-2]
c=0
s=[0 for i in range(n+1)]
for i in range(1,n+1):
  s[i]=s[i-1]+a[i-1]
for i in range(n):
  for j in range(i+1,n+1):
    if (s[j]-s[i])==0:
      c+=1
print(c)

### FIXED CODE ###

import collections

n=int(input())
a=list(map(int,input().split(" ")))
#n=5
#a=[1,-2,3,-4,5]
s=[0 for i in range(n+1)]
for i in range(1,n+1):
  s[i]=s[i-1]+a[i-1]
c=collections.Counter(s).most_common()
d=0
for i in c:
  if i[1]<2:
    break
  d+=i[1]*(i[1]-1)//2
print(d)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]

A.sort()
B.sort()
C.sort()

A_pat = [0] * N
B_pat = [0] * N

c = 0
for b in range(N):
    for i in range(c,N):
        if B[b] < C[i]:
            c = i
            B_pat[b] = N-i
            break

B_pat_sum = [0]*N
B_pat_sum[N-1] = B_pat[N-1]
for i in range(N-2,-1,-1):
    B_pat_sum[i] = B_pat_sum[i+1] + B_pat[i]

b = 0
for a in range(N):
    for i in range(b,N):
        if A[a] < B[i]:
            b = i
            A_pat[a] = B_pat_sum[i]
            break
print(sum(A_pat))


### FIXED CODE ###

N = int(input())
A = [[int(a),"A"] for a in input().split()]
B = [[int(b),"B"] for b in input().split()]
C = [[int(c),"C"] for c in input().split()]

parts = A+B+C
parts.sort(key = lambda x:x[1])
parts.sort(reverse = True,key = lambda x:x[0])

A_pat = [0]  
B_pat = [0]
C_count = 0

for s,t in parts:
    if t=="C":      
        C_count += 1
    elif t=="B":
        B_pat.append(C_count+B_pat[-1])
    elif t=="A":
        A_pat.append(B_pat[-1]+A_pat[-1])
print(A_pat[-1])
### BUGGY CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    if check(i):
        count=0
        for j in range(N):
            count += ((i >> j) & 1)
            if count > best:best = count
	
print(best)

### FIXED CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
D = [[0]*W for i in range(H)]
mx = 1
for i in range(H):
    for j in range(W):
        D[i][j] = abs(A[i][j]-B[i][j])
        mx = max(mx, D[i][j])
MX = mx*(H+W)
dp = [[[0]*(MX+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][D[0][0]] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in range(MX+1):
            if dp[i][j][k]:
                if j+1 <= W:
                    d = D[i-1][j]
                    if k+d <= MX:
                        dp[i][j+1][k+d] = 1
                    dp[i][j+1][abs(k-d)] = 1
                if i+1 <= H:
                    d = D[i][j-1]
                    if k+d <= MX:
                        dp[i+1][j][k+d] = 1
                    dp[i+1][j][abs(k-d)] = 1
#for i in range(H+1):
#    for j in range(W+1):
#        print(i, j)
#        print(dp[i][j])
for i in range(MX+1):
    if dp[H][W][i]:
        print(i)
        exit()


### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
D = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        D[i][j] = abs(A[i][j]-B[i][j])
buf = 80*(H+W)
dp = [[0]*W for i in range(H)]
dp[0][0] = 1<<(buf+D[0][0]) | 1<<(buf-D[0][0])
for i in range(H):
    for j in range(W):
        d = D[i][j]
        if i:
            dp[i][j] |= dp[i-1][j]<<d | dp[i-1][j]>>d
        if j:
            dp[i][j] |= dp[i][j-1]<<d | dp[i][j-1]>>d
ans = 10**18
for i in range(buf*2+1):
    if dp[H-1][W-1]&(1<<i):
        ans = min(ans, abs(buf-i))
print(ans)
### BUGGY CODE ###

q = int(input())

def lcs(X, Y):
    x_len = len(X)
    y_len = len(Y)
    dp = [[0 for _ in range(y_len+1)] for _ in range(x_len+1)]
    
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                               
    return max(max(dp))
    
for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

### FIXED CODE ###

q = int(input())

def lcs(X, Y):
    dp = [0]*(len(Y)+1)
    
    for x in X:
        tmp = dp[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                               
    return dp[-1]
    
for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [list(SS()) for _ in range(H)]

    left = [[0] * W for _ in range(H)]
    for i in range(H):
        cnt = 0
        for j in range(W):
            if S[i][j] == '.':
                cnt += 1
                left[i][j] = cnt
            else:
                cnt = 0

    right = [[0] * W for _ in range(H)]
    for i in range(H):
        cnt = 0
        for j in range(W):
            if S[i][W-1-j] == '.':
                cnt += 1
                right[i][W-1-j] = cnt
            else:
                cnt = 0

    up = [[0] * W for _ in range(H)]
    for i in range(W):
        cnt = 0
        for j in range(H):
            if S[j][i] == '.':
                cnt += 1
                up[j][i] = cnt
            else:
                cnt = 0

    down = [[0] * W for _ in range(H)]
    for i in range(W):
        cnt = 0
        for j in range(H):
            if S[H-1-j][i] == '.':
                cnt += 1
                down[H-1-j][i] = cnt
            else:
                cnt = 0

    ans = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            ans[i][j] = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3

    print(max([max(i) for i in ans]))

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    S = [list(SS()) for _ in range(H)]

    idx_w = []
    for i in range(H):
        tmp = [-1]
        for j in range(W):
            if S[i][j] == '#':
                tmp.append(j)
        tmp.append(W)
        idx_w.append(tmp)

    idx_h = []
    for i in range(W):
        tmp = [-1]
        for j in range(H):
            if S[j][i] == '#':
                tmp.append(j)
        tmp.append(H)
        idx_h.append(tmp)

    ans = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(len(idx_w[i]) - 1):
            for k in range(idx_w[i][j] + 1, idx_w[i][j+1]):
                ans[i][k] += idx_w[i][j+1] - idx_w[i][j] - 1

    for i in range(W):
        for j in range(len(idx_h[i]) - 1):
            for k in range(idx_h[i][j] + 1, idx_h[i][j+1]):
                ans[k][i] += idx_h[i][j+1] - idx_h[i][j] - 2

    # for i in ans:
    #     print(i)

    print(max([max(i) for i in ans]))

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

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
count = 0
for i in range(n):
    while xh[i][1] > 0:
        r = xh[i][0] + d*2
        atack = -(-xh[i][1]//a)
        xh[i][1] = 0
        count += atack
        if i > n-1: continue
        j = i
        while True:
            j += 1
            if j<n and r>=xh[j][0]: xh[j][1] -= atack*a
            else: break
print(count)

### FIXED CODE ###

from collections import deque
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for i in range(n)]
xh.sort()
que = deque()
ans = 0
atk = 0
for x, h in xh:
    while que and que[0][0] <= x:
        atk -= que.popleft()[1]
    h -= a*atk
    if h <= 0:
        continue
    count = -(-h//a)
    ans += count
    atk += count
    que.append((x+2*d+1, count))
print(ans)