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

from bisect import bisect_left as bl

def search_left(in_ind, alst, outs, doors):
  tmp = bl(outs, in_ind)
  if tmp == 0:
    return 0
  out_ind = outs[tmp - 1]

  right_door = bl(doors, in_ind) - 1
  if right_door < 0:
    return alst[in_ind]
  left_door = bl(doors, out_ind)
  
  ret = alst[in_ind]
  for door_ind in doors[left_door:right_door + 1]:
    if out_ind < door_ind < in_ind:
      ret = min(ret, -alst[door_ind] - (in_ind - door_ind))
  ret = max(0, ret)
  return ret

def search_right(in_ind, alst, outs, doors):
  tmp = bl(outs, in_ind)
  if tmp == len(outs):
    return 0
  out_ind = outs[tmp]

  right_door = bl(doors, out_ind) - 1
  if right_door < 0:
    return alst[in_ind]
  left_door = bl(doors, in_ind)

  ret = alst[in_ind]
  for door_ind in doors[left_door:right_door + 1]:
    if in_ind < door_ind < out_ind:
      ret = min(ret, -alst[door_ind] - (door_ind - in_ind))
  ret = max(0, ret)
  return ret

def main():
  w = int(input())
  alst = list(map(int, input().split()))
  outs = []
  ins = []
  doors = []
  for ind, a in enumerate(alst):
    if a > 0:
      ins.append(ind)
    elif a == 0:
      outs.append(ind)
    else:
      doors.append(ind)
  ans = 0
  for in_ind in ins:
    ans += max(search_left(in_ind, alst, outs, doors), search_right(in_ind, alst, outs, doors))
  print(ans)
main() 


### FIXED CODE ###

w = int(input())
alst = list(map(int, input().split()))
INF = 10 ** 20
acc = -INF
left = []
for i in range(w):
  a = alst[i]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  left.append(acc)

acc = -INF
right = []
for i in range(w):
  a = alst[w - i - 1]
  if a == 0:
    acc = INF
  elif a > 0:
    acc -= 1
  elif a < 0:
    acc = min(acc - 1, -a)
  right.append(acc)
right.reverse()

print(sum([max(0, min(alst[i], max(left[i], right[i]))) for i in range(w)]))
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(1, N+1):
    ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(1, N+1):
    ans *= i
    if ans >= (10**9 + 7):
        ans %= (10**9+7)
print(ans)
### BUGGY CODE ###

N, Q = [int(nq) for nq in input().split()]
S = input()
ANS = []
for q in range(Q):
    l, r = [int(lr) for lr in input().split()]
    ans = S[l-1:r].count("AC")
    print(ans)

### FIXED CODE ###

N, Q = [int(nq) for nq in input().split()]
S = input()
AC = []
for s in range(len(S)-1):
    if S[s:s+2] == "AC":
        AC.append(1)
    else:
        AC.append(0)
CS = [0]*len(AC)
CS[0] = AC[0]
for i in range(len(AC)-1):
    CS[i+1] = CS[i] + AC[i+1]
for q in range(Q):
    l, r = [int(lr) for lr in input().split()]
    if l == 1:
        print(CS[r-2])
    else:
        print(CS[r-2] - CS[l-2])
### BUGGY CODE ###

import bisect
class BinaryIndexedTree():
    def __init__(self,size):
        self.BIT = [0]*(size+1)
    def query(self,index):
        #sum of A1 ~ Ai O(logN)
        ret=0
        while index > 0:
            ret += self.BIT[index]
            index -= index & (-index)
        return ret
    def update(self,index,x):
        #add x to Ai O(logN)
        while index <=  len(self.BIT)-1:
            self.BIT[index] += x
            index += index & (-index)
        return
n=int(input())
a=list(map(int,input().split()))
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=2*max(a)+20
ok=0
while ng-ok>1:
    check=(ok+ng)//2
    cnt=0 #check以上の要素の数
    s=[0]*(n+1)
    B=BinaryIndexedTree(n+1)
    for i in range(1,n+1):
        if a[i-1]<check:s[i]=s[i-1]-1
        else:s[i]=s[i-1]+1
    
    # 座標圧縮
    S=sorted(s)
    for i,e in enumerate(s):
        s[i]=bisect.bisect_left(S,e)
    for i,e in enumerate(s):
        cnt += B.query(e+1)
        B.update(e+1,1)
    if cnt >= ((n+1)*n)//4:
        ok = check
    else:
        ng = check
print(ok)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a2=sorted(set(a))
L=len(a2)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=L
ok=0
while ng-ok>1:
    check=a2[(ok+ng)//2]
    cnt=0 #check以上の要素の数
    idx=n
    cl=[0]*(2*n+1)
    cl[n]=1
    Ru=0
    for i in range(n):
        if a[i]<check:
            Ru-=cl[idx]-1
            idx-=1
        else:
            idx+=1
            Ru+=cl[idx]+1
        cnt += Ru
        cl[idx]+=1
    if cnt >= ((n+1)*n//2)//2:
        ok = (ok+ng)//2
    else:
        ng = (ok+ng)//2
print(a2[ok])
### BUGGY CODE ###

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

n,m,l = map(int,input().split())
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
wf.build()
d = [[1e100]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            d[i][j] = 0
        elif wf.d[i][j] <= l:
            d[i][j] = 1

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

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


### FIXED CODE ###

import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = []
        for i in range(n):
            self.d.append([1e100]*n)
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

n,m,l = map(int,input().split())
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
d = wf.build()

wf = WarshallFloyd(n)
for i in range(1,n):
    for j in range(i):
        if d[i][j] <= l:
            wf.path(i,j,1)

ans = wf.build()

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

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

N = int(input())
S = [Counter(input()) for _ in range(N)]

ans = 0
T = []
ans = [1]*N
for i in range(N):
    if S[i] in T:
        p = T.index(S[i])
        ans[p] += 1
    else:
        T.append(S[i])

pp = 0
for i in ans:
    pp += (i-1)*i//2

print(pp)


### FIXED CODE ###

from collections import Counter, defaultdict

N = int(input())
S = [Counter(input()) for _ in range(N)]

dd = defaultdict(int)

for i in S:
    p = 0
    for j in i:
        p += 26**(ord(j)-ord('a'))*(i[j])
    dd[p] += 1

ans = 0
a = dd.keys()
for i in a:
    ans += (dd[i]-1)*dd[i]//2
print(ans)
### BUGGY CODE ###

N , M = map(int,input().split())
H = list(map(int,input().split()))

lst = list(range(1,N+1))
for i in range(M):
    A_,B_ = map(int,input().split())
    if H[A_ -1] >= H[B_ -1]:
        if B_ in lst:
            lst.remove(B_)
    if H[A_-1] <= H[B_- 1]:
        if A_ in lst:
            lst.remove(A_)
print(len(lst))


### FIXED CODE ###

N , M = map(int,input().split())
H = list(map(int,input().split()))

lst = []
for i in range(M):
    A_,B_ = map(int,input().split())
    if H[A_ -1] >= H[B_ -1]:
        lst.append(B_)
    if H[A_-1] <= H[B_- 1]:
        lst.append(A_)
print(N - len(set(lst)))
### BUGGY CODE ###

N, M, Q = map(int,input().split())

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1

for j in range(Q):
	p,q = map(int,input().split())
	s = 0
	for i in range(p,q+1):
		for j in range(i,q+1):
#			print((i,j))
			s += C[i][j]
	print(s)


### FIXED CODE ###

N, M, Q = map(int,input().split())

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
E = [0 for i in range(N+4)]
F = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]
for i in range(N+1):
	E[i+1] = E[i] + D[i][i]
for i in range(N+2):
	for j in range(N+2):
		F[i+1][j] = F[i][j] + D[i][j]

# C[l][l] + ... + C[l][r] = D[l][r+1] - D[l][l]
# C[i][i] + ... + C[i][r] = D[i][r+1] - D[i][i]
# C[r][r] + ... + C[r][r] = D[r][r+1] - D[r][r]

for j in range(Q):
	p,q = map(int,input().split())
	s = F[q+1][q+1] - F[p][q+1] - (E[q+1] - E[p])
	print(s)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

print(sum(range(1, N)))


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

print(N*(N-1)//2)
### BUGGY CODE ###

from itertools import accumulate

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

for _ in range(K):
    if A == [N] * N:
        break
    B = [0] * (N+1)
    for i, a in enumerate(A):
        start = max(0, i - a)
        end = min(N-1, i + a) + 1
        B[start] += 1
        B[end] -= 1
        A = list(accumulate(B))[:-1]
print(' '.join(map(str, A)))



### FIXED CODE ###

from itertools import accumulate

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

for _ in range(K):
    if A == [N] * N:
        break
    B = [0] * (N+1)
    for i, a in enumerate(A):
        start = max(0, i - a)
        end = min(N-1, i + a) + 1
        B[start] += 1
        B[end] -= 1
    A = list(accumulate(B))[:-1]
print(' '.join(map(str, A)))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

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

N = int(input())
alist = list(map(int, input().split()))
    
ans = []
for i in range(N):
  sign = 1
  mi = 0
  for j in range(i,i+N):
    if j <= N-1:
      mi += sign*alist[j]
    else:
      mi += sign*alist[j-(N)]
    sign *= -1
  ans.append(mi)
print(*ans)

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
m1, m2 = 0, 0
for i, a in enumerate(alist):
  if i == 0:
    m1+=a
    m2+=a
  elif i%2 == 0:
    m1+=a
    m2+=-1*a
  else:
    m1+=-1*a
    m2+=a    

ans = [m1, m2]
for i in range(2, N-1, 2):
  # index=i
  ans.append(ans[i-2] -2*alist[i-2] + 2*alist[i-1])
  # index=i+1
  ans.append(ans[i-1] - 2*alist[i-1] + 2*alist[i])

ans.append(ans[N-3] - 2*alist[N-3] + 2*alist[N-2])

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

# coding: utf-8
# Your code here!

N = int(input())
L = list(map(int, input().split()))

# print(N)
# print(L)

L_sorted = sorted(L)
# print(L_sorted)

count = 0
for i in range(0, N - 2):
    # print(i)
    for j in range(i + 1, N - 1):
        # print(j)
        for k in range(j + 1, N):
            a = L_sorted[i]
            b = L_sorted[j]
            c = L_sorted[k]
            
            if a + b <= c:
                break
            # print('{}, {}, {}'.format(a, b, c))
            count += 1
        
print(count)        

### FIXED CODE ###

# coding: utf-8
# Your code here!

import bisect

N = int(input())
L = list(map(int, input().split()))

# print(N)
# print(L)

L_sorted = sorted(L)
# print(L_sorted)

count = 0
for i in range(0, N - 2):
    # print(i)
    for j in range(i + 1, N - 1):
        a = L_sorted[i]
        b = L_sorted[j]
        # print(j)
        # for k in range(j + 1, N):
        #     a = L_sorted[i]
        #     b = L_sorted[j]
        #     c = L_sorted[k]
            
        #     if a + b <= c:
        #         break
        #     # print('{}, {}, {}'.format(a, b, c))
        #     count += 1
        
        # print('{}, {},'.format(a, b))
        index = bisect.bisect_left(L_sorted, a + b, i + 1, N)
        # print(index)
        # print((index - 1) - j)
        count += ((index - 1) - j)
        
print(count)
### BUGGY CODE ###

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

ans = 1

for a in A:
    ans *= a
if ans > pow(10, 18):
    ans = -1
print(ans)


### FIXED CODE ###

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

ans = 1

if 0 in A:
    ans = 0
else:
    for a in A:
        ans *= a
        if ans > pow(10, 18):
            ans = -1
            break
print(ans)
### BUGGY CODE ###

N = input()
P = list(map(int, input().split()))
count = 0
for i in range(int(N)):
    temp = 0
    for j in range(i+1):

        if P[i] <= P[j]:
            temp = temp + 1
        else:
            temp =0
    if temp == j+1:
        count = count + 1
print(count)
            

### FIXED CODE ###

N = input()
P = list(map(int, input().split()))
count = 0

now_mini= 1<<20
for i in P:
    if i < now_mini:
        count = count + 1
        now_mini=i
print(count)
### BUGGY CODE ###

import sys

input = lambda: sys.stdin.readline().rstrip()


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def max_index(self):

        i = 0

        while True:
            l, r = i * 2 + 1, i * 2 + 2
            if self.seg[l] < self.seg[r]:
                i = r
            else:
                i = l
            if i * 2 + 2 >= len(self.seg):
                break
        return (i - (self.num - 1), self.seg[0])


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def solve():

    seg = [A[i] * F[i] for i in range(N)]
    segtree = SegTree(seg, segfunc=max, ide_ele=0)

    for _ in range(K):
        i, num = segtree.max_index()
        if num == 0:
            break
        else:
            A[i] -= 1
            segtree.update(i, A[i] * F[i])

    i, num = segtree.max_index()
    print(num)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    for i in range(N):
        if A[i] * F[i] > tn:
            k += A[i] - (tn // F[i])
        if k > K:
            return False

    return True


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


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

n = int(input())
num = list(map(int,input().split()))
for i in range(n):
    for j in range(n):
        if (i+1) == num[j]:
            print(j+1, end=" ")


### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
num_array = [0]*n
for i in range(n):
    num_array[num_list[i]-1] = i+1
for i in range(n):
    print(num_array[i])
### BUGGY CODE ###

from math import floor, ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    lower = 1
    upper = a[-1]
    for _ in range(10000):
        target = (lower + upper) / 2
        now = 0
        for i in range(n):
            now += ceil(a[i] / target) - 1
        if now > k:
            lower = target
        else:
            upper = target
    print(ceil(lower) if k > 0 else a[-1])


if __name__ == '__main__':
    main()



### FIXED CODE ###

from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = 10 ** 9 + 7
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


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

A,B,N=map(int,input().split())

s=0
if B<=N:
  x=B-1
  s=(A*x)//B - A*(x//B)
else:
  for x in range(1,N+1):
    p = (A*x)//B - A*(x//B)
    if p<s:
      break
    if p>s:
      s=p
print(s)

### FIXED CODE ###

A,B,N=map(int,input().split())

s=0
if B<=N:
  x=B-1
  s=(A*x)//B - A*(x//B)
else:
  x=N
  s=(A*x)//B - A*(x//B)
print(s)
### BUGGY CODE ###

S=input()
T=input()
N=[i for i in range(len(S))]
visited=[]

for i in N:
    if (S[i] not in visited) and S[i]!=T[i]:
        visited.append(T[i])
        x=S[i]
        S=S.replace(T[i],'_')
        S=S.replace(S[i],T[i])
        S=S.replace('_',x)
    elif S[i] in visited and S[i]!=T[i]:
        break
    else:
        visited.append(T[i])
print('No') if S!=T else print('Yes')

### FIXED CODE ###

S=input()
T=input()
R=[-1]*26
R2=[-1]*26
flag=1

for i in range(len(S)):
    a=ord(S[i])-97
    b=ord(T[i])-97
    if R[a]!=-1 or R2[b]!=-1:
        if R[a]!=b or R2[b]!=a:
            flag=0
            break
    else:
        R[a]=b
        R2[b]=a
if flag==0:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

m = 10**9 + 7
n = input()
a = list(map(int,input().split()))
ans = 0

for i in range (len(a)):
  for j in range (i+1,len(a)):
    ans += a[i]*a[j]

ans = ans%m

print(ans)

### FIXED CODE ###

m = 10**9 + 7
n = input()
a = list(map(int,input().split()))
ans = 0
s = sum(a)

for i in a:
  s -= i
  ans += s*i

ans = ans%m

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

import sys
def prime(n):
  l = [2]
  for i in range(3,n+1):
    count = 0
    for j in l:
      if i % j == 0:
        count += 1
    if count == 0:
      l.append(i)
  return l
for line in sys.stdin.readlines():
  n = int(line)
  if n == 1:
    print(0)
  else:
    print(len(prime(n)))

### FIXED CODE ###

lst = [1 for i in range(10 ** 6 + 1)]
lst[0] = lst[1] = 0
for i in range(10 ** 6 + 1):
  if lst[i] == 1:
    for j in range(i * 2, 10 ** 6 + 1, i):
      lst[j] = 0
while 0 == 0:
  try:
    n = int(input())
    c = 0
    for i in range(n + 1):
      c += lst[i]
    print(c)
  except EOFError:
    break
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
d = 0
if A[0][0]=="#":
    d += 1
que = deque([(0,0,d)])
hist = [[H*W for _ in range(W)] for _ in range(H)]
hist[0][0] = d
while que:
    i,j,d = que.popleft()
    if j+1<W and A[i][j+1]==A[i][j]:
        hist[i][j+1] = min(hist[i][j+1],d)
        que.append((i,j+1,hist[i][j+1]))
    elif j+1<W and A[i][j+1]!=A[i][j]:
        hist[i][j+1] = min(hist[i][j+1],d+1)
        que.append((i,j+1,hist[i][j+1]))
    if i+1<H and A[i+1][j]==A[i][j]:
        hist[i+1][j] = min(hist[i+1][j],d)
        que.append((i+1,j,hist[i+1][j]))
    elif i+1<H and A[i+1][j]!=A[i][j]:
        hist[i+1][j] = min(hist[i+1][j],d+1)
        que.append((i+1,j,hist[i+1][j]))
m = hist[H-1][W-1]
print((m+1)//2)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
d = 0
if A[0][0]=="#":
    d += 1
que = deque([(0,0,d)])
hist = [[H*W for _ in range(W)] for _ in range(H)]
hist[0][0] = d
while que:
    i,j,d = que.popleft()
    if j+1<W and A[i][j+1]==A[i][j]:
        if hist[i][j+1]>d:
            hist[i][j+1] = d
            que.append((i,j+1,d))
    elif j+1<W and A[i][j+1]!=A[i][j]:
        if hist[i][j+1]>d+1:
            hist[i][j+1] = d+1
            que.append((i,j+1,d+1))
    if i+1<H and A[i+1][j]==A[i][j]:
        if hist[i+1][j]>d:
            hist[i+1][j] = d
            que.append((i+1,j,d))
    elif i+1<H and A[i+1][j]!=A[i][j]:
        if hist[i+1][j]>d+1:
            hist[i+1][j] = d+1
            que.append((i+1,j,d+1))
m = hist[H-1][W-1]
print((m+1)//2)
### BUGGY CODE ###

H, W, M = map(int, input().split())
targets = [list(map(int, input().split())) for _ in range(M)]
x_counter = [0 for _ in range(W + 1)]
y_counter = [0 for _ in range(H + 1)]
y_index = []
x_index = []
dup = True

for target in targets:
    y_counter[target[0]] += 1
    x_counter[target[1]] += 1

y_max, x_max = max(y_counter), max(x_counter)

for i in range(H + 1):
    if y_counter[i] == y_max:
        y_index.append(i)

for j in range(W + 1):
    if x_counter[j] == x_max:
        x_index.append(j)

for k in y_index:
    for l in x_index:
        if [k, l] not in targets:
            print(y_max + x_max)
            exit()

print(y_max + x_max - 1)


### FIXED CODE ###

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)
### BUGGY CODE ###

N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
ans = 0
import bisect
while E:
    x = E.pop(0)
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = d[x]
    ans += z
    for k in range(y):
        d[E[k]] -= z 
print(ans)


### FIXED CODE ###

N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)