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

#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    a = list(map(int, readlines()))
    diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    if 1 in diff_a:
        print(0)
        return
    p1, p2 = 0, 1
    if 1 not in a:
        p1 = 1

    for i in range(2, n + 1):
        if i in a:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


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

N = int(input())
A = list(map(int, input().split()))
INF = float("inf")
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            tmp = B[j] + B[j ^ (1 << i)]
            tmp = sorted(tmp, reverse=True)
            B[j] = tmp[:2]

ans = -INF
for i in range(1, 1 << N):
    ans = max(ans, sum(B[i]))
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = float("inf")
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            tmp = B[j] + B[j ^ (1 << i)]
            tmp = sorted(tmp, reverse=True)
            B[j] = tmp[:2]

ans = -INF
for i in range(1, 1 << N):
    ans = max(ans, sum(B[i]))
    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
b = [int(input()) for _ in range(m)]
A = [0,1]
if 0 in b:
  print(0)
else:
  for i in range(1,n+1):
    if i in b:
      A.append(0)
    else:
      A.append( (A[-1]+A[-2]) % (10**9+7) )
  print(A[-1])

### FIXED CODE ###

n,m = map(int,input().split())
b = [int(input()) for _ in range(m)] + [n+1]
now = 0
A = [0,1]
if b[0] == 0:
  print(0)
else:
  for i in range(1,n+1):
    if b[now] == i:
      A.append(0)
      now += 1
    else:
      A.append( (A[-1]+A[-2]) % (10**9+7) )
  print(A[-1])
### BUGGY CODE ###

import math
from functools import reduce
from math import gcd
K = int(input())
A=[]
B=[]
sum = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        A.append(gcd(a,b))
for x in range(len(A)):
    for c in range(1,K+1):
        B.append(gcd(A[x],c))
for i in range(len(B)):
    sum +=B[i]
print(sum)

### FIXED CODE ###

import math
 
 
N = int(input())
 
s = 0
 
for i in range(N):
    for j in range(N):
        ss = math.gcd(i+1,j+1)
        for k in range(N):
            s +=math.gcd(ss,k+1)
 
print(s)
### BUGGY CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
print(solve(N,A,X))


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

def solve():
    N = int(raw_input())
    Di = []
    sum = 0
    for i in range(N):
        di = int(raw_input())
        sum += di
        Di.append([i, di])
    if sum % 2 > 0:
        print '-1'
        return
    Di.sort(key = lambda x : x[1])
    d_to_i = {di[1]:di[0] for di in Di}
    # child = [[] for i in range(N)]
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    root_node = None
    for ind in range(N - 1, -1, -1):
        node = Di[ind][0]
        valD_par = Di[ind][1] - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            # child[node].append(node_par) ##
            # child[node_par].append(node)
            ans.append([node_par + 1, node + 1])
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
        else:
            print '-1'
            return
        if n_child[node_par] == N:
            root_node = node_par
            break
    # check if Di satisfied or not
    if root_node is not None and d_child[root_node] != Di[0][1]:
        print '-1'
        return
    # for i in range(N):
    #     for j in child[i]:
    #         print str(i + 1) + ' ' + str(j + 1)
    for ele in ans:
        print str(ele[0]) + ' ' + str(ele[1])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)
### BUGGY CODE ###

from itertools import product
N, M = map(int, input().split())
INF = 10 ** 12
dp = [INF] * (2**N)
pp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    # dp[i]
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    base = sum(2**(c-1) for c in C)
    for j in range(2**N):
        if any(not ((j >> (c-1)) & 1) for c in C):
            step = base - sum(2**(c-1) for c in C if ((j >> (c-1)) & 1))
            dp[j+step] = min(dp[j+step], dp[j]+a)

print(dp[-1] if dp[-1] < INF else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
INF = 10 ** 12
T = [2**i for i in range(N)]
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    step = sum(T[c-1] for c in C)
    for j in range(2**N):
        dp[step|j] = min(dp[step|j], dp[j]+a)

print(dp[-1] if dp[-1] < INF else -1)
### BUGGY CODE ###

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

j = 1
for i in range(1,N):
  sort_list = sorted(p_list[0:i+1])
  if p_list[i] <= sort_list[0]:
    j = j + 1

print(j)

### FIXED CODE ###

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

j = 1
temp = p_list[0]
for i in range(1,N):
  if temp >= p_list[i]:
    j += 1
    temp = min(temp,p_list[i])

print(j)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# メモ化関数定義
def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
@memoize
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

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

from bisect import bisect_left
n = int(input())
llist = list(map(int, input().split()))

llist.sort()
res = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        rest = llist[j+1:]
        num = llist[i] + llist[j] 
        idx = bisect_left(rest, num)
        res += idx

print(res)

### FIXED CODE ###

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

llist.sort()
res = 0
for i in range(n-2):
    prev = n-1
    for j in range(n-2,i,-1):
        for k in range(prev, j, -1):
            if llist[k] < llist[i] + llist[j]:
                res += k - j
                prev = k
                break            
print(res)
### BUGGY CODE ###

def solve(string):
    h, w, k = map(int, string.split())
    c = [1, 1]
    for _ in range(1, 7):
        i, j = c[-2:]
        c.append(i + j)

    def rec(pos, depth):
        if depth == h:
            return 1 if pos == 1 else 0
        ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
        if pos < w:
            ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
        if pos > 1:
            ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
        return ans

    return str(rec(k, 0) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

from functools import lru_cache


def solve(string):
    h, w, k = map(int, string.split())
    c = [1, 1]
    for _ in range(1, 7):
        i, j = c[-2:]
        c.append(i + j)

    @lru_cache(h * w)
    def rec(pos, depth):
        if depth == h:
            return 1 if pos == 1 else 0
        ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
        if pos < w:
            ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
        if pos > 1:
            ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
        return ans

    return str(rec(k, 0) % (10**9 + 7))


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

n = int(input())
counta=0
tmp=n

for a in range(1,n):
    for b in range(1,n):
        #print(a,b)
        if a * b +1 <= n:
            counta+=1
        else:
            break
print(counta)

### FIXED CODE ###

n = int(input())
counta=0
for a in range(1,n):
    for b in range(1,n):
        #print(a,b)
        if a * b +1 <= n:
            counta+=1
        else:
            break
print(counta)
### BUGGY CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(input())

used = [True]*(h*w)

p = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            p.append(i*w+j)
            used[i*w+j] = False
 
 
res = 0
while p:
    tank = []
    for e in p:
        if e>w-1 and used[e-w]:
            tank.append(e-w)
            used[e-w] = False
        if e%w > 0 and used[e-1]:
            tank.append(e-1)
            used[e-1] = False
        if e<(h-1)*w and used[e+w]:
            tank.append(e+w)
            used[e+w] = False
        if e%w<w-1 and used[e+1]:
            tank.append(e+1)
            used[e+1] =  False
    p = tank
    res += 1
print(res-1)

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
DP = [float('inf')]*N
DP[0] = 0
for i in range(0,N):
    for j in range(i+1,min(N,i+K+1)):
        DP[j] = min(DP[j],DP[i]+abs(h[i]-h[j]))
print(DP[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
DP = [float('inf')]*N
DP[0] = 0
for i in range(N):
    for j in range(K):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(n-k+1):
    e = sum(p[i:i+k])/2 + k/2
    if ans < e:
        ans = e
print(ans)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

s_list = [0]*(n+1)
s_list[1] = p[0]
for i in range(1, n+1):
    s_list[i] = p[i-1] + s_list[i-1]

for i in range(n-k+1):
    e = (s_list[i+k] - s_list[i] + k)/2
    if ans < e:
        ans = e
print(ans)
### BUGGY CODE ###

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

def calc_plus(n):
  return n + 1

if K > N-1:
  list1 = [N]*N
  A = list1

for k in range(K):
  list1 = [0]*N
  for i in range(N):
    num1 = max(0, i-A[i])
    num2 = min(i+A[i]+1, N)
    list1 = list1[0:num1] + list(map(calc_plus, list1[num1:i]))+list1[i:i+1] +list(map(calc_plus, list1[i+1:num2])) + list1[num2:N]
  list1 = list(map(calc_plus, list1))
  A = list1
  
for l in range(N):
  print(A[l], end=" ")
  

### FIXED CODE ###

#%%time
from itertools import accumulate
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def loop1(a):
  #b = [0]*(n+1)
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int, input().split()))
for i in range(n):
	p[i]=(1+p[i])/2
ans=0
for i in range(n-k+1):
	ans=max(ans,sum(p[i:i+k]))
print('{:.8f}'.format(ans))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int, input().split()))
for i in range(n):
	p[i]=(1+p[i])/2
cs=[]
sum=0
for i in range(n):
	sum+=p[i]
	cs.append(sum)
ans=cs[k-1]
for i in range(1,n-k+1):
	ans=max(ans,cs[i+k-1]-cs[i-1])
print('{:.8f}'.format(ans))
### BUGGY CODE ###

import collections

n = int(input())
a = []
max_list = []
max_i = 1

for i in range(n):
    a.append(str(input()))

c = collections.Counter(a)
max_i = c.most_common()[0][1]

max_list = [x for x in set(a) if a.count(x) == max_i]

max_list.sort()

for i in max_list:
    print(i)       
    

### FIXED CODE ###

import collections

n = int(input())
a = []
max_list = []
max_i = 1

a = [str(input()) for x in range(n)]

c = collections.Counter(a)
c = c.most_common()
max_i = c[0][1]

for i in range(len(c)):
    if max_i == c[i][1]:
        max_list.append(c[i][0])
    else:
        break

max_list.sort()

for i in max_list:
    print(i)
### BUGGY CODE ###

G={chr(a+ord("a")):a for a in range(26)}
H={G[b]:b for b in G}

T=input()
S=[]
for s in T:
    S.append(G[s])
K=int(input())

I=0
N=len(S)
for i in range(N):
    if (i!=N-1) and (26-S[i]<=K):
        K-=26-S[i]
        S[i]=0
    elif i==N-1:
        S[i]=(S[i]+K)%26

U=""
for s in S:
    U+=H[s]

print(U)


### FIXED CODE ###

G={chr(a+ord("a")):a for a in range(26)}
H={G[b]:b for b in G}

T=input()
S=[]
for s in T:
    S.append(G[s])
K=int(input())

I=0
N=len(S)
for i in range(N):
    if (i<N-1) and (26-S[i]<=K) and S[i]!=0:
        K-=26-S[i]
        S[i]=0
    elif i==N-1:
        S[i]=(S[i]+(K%26))%26

U=""
for s in S:
    U+=H[s]

print(U)
### BUGGY CODE ###

def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      dp[i][-1]=0
      for j in range(N-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j]%mod
    else:
      dp[i][0] = 0
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j]%mod
  ans = sum(dp[0])%mod
  return ans
print(solve())

### FIXED CODE ###

def solve():
  N = int(input())
  s = input()
  mod = 10**9+7
  dp = [[0]*N for _ in range(N)]
  dp[-1][0]=1
  for i in range(N-2,-1,-1):
    if s[i]=='>':
      for j in range(N-i-2,-1,-1):
        dp[i][j] = dp[i][j+1]+dp[i+1][j]
        dp[i][j] %= mod
    else:
      for j in range(1,N-i):
        dp[i][j] = dp[i][j-1]+dp[i+1][j-1]
        dp[i][j] %= mod
  ans = sum(dp[0])%mod
  return ans
print(solve())
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            n = 0
            while str(i) != S[n] and n < N-3:
                n += 1
            if S[n] != str(i):
                break
            n += 1
            while str(j) != S[n] and n < N-2:
                n += 1
            if S[n] != str(j):
                break
            n += 1
            while str(k) != S[n] and n < N-1:
                n += 1
            if S[n] == str(k):
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
snumber = [str(i) for i in range(10)]
for i in snumber:
    for j in snumber:
        for k in snumber:
            n = 0
            code = []
            while i != S[n] and n < N-3:
                n += 1
            if S[n] != i:
                break
            n += 1
            while j != S[n] and n < N-2:
                n += 1
            if S[n] != j:
                break
            n += 1
            while k != S[n] and n < N-1:
                n += 1
            if S[n] == k:
                ans += 1
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    for idx, i in enumerate(P):
        for j in P[:idx]:
            if i > j:
                break
        else:
            n += 1
    print(n)

resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    x = 10 ** 20
    for i in range(N):
        if x >= P[i]:
            x = P[i]
            n += 1
    print(n)

resolve()
### BUGGY CODE ###

N, K, Q = map(int, input().split())
a = [int(input()) for i in range(Q)]
score = [a.count(x) for x in range(1, N+1)]
yn = ['No', 'Yes']

ans = [yn[min(1,max(K+x-Q,0))] for x in score]

for y in ans:
    print(y)

### FIXED CODE ###

N, K, Q = map(int, input().split())
a = [int(input()) for i in range(Q)]

score = [0 for i in range(N)]
for x in a:
    score[x-1] += 1

yn = ['No', 'Yes']
ans = [yn[min(1,max(K+x-Q,0))] for x in score]

for y in ans:
    print(y)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]
  XH.sort(key=lambda x:x[0])
  #print(XH)

  B = []
  ans = 0
  for x,h in XH:
    BB = []
    for s,t,c in B:
      #print(s,t,c,x)
      if s <= x <= t:
        h -= A*c
        BB.append((s,t,c))
    #print(h)
    if h > 0:
      BB.append((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
    #print(ans,x,x+2*D,(h+A-1)//A,B)
    B = BB[:]
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

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

H, W, D = map(int, input().split())
A = {}

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        A[row[j]] = [i+1, j+1]

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    ans = 0
    while L != R:
        ans += abs(A[L+D][0] - A[L][0]) + abs(A[L+D][1] - A[L][1])
        L += D
    print(ans)


### FIXED CODE ###

H, W, D = map(int, input().split())
A = {}

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        A[row[j]] = [i+1, j+1]

Q = int(input())
ANS = [0] * (H * W + 1)

for i in range(D+1, H * W +1):
    ANS[i] = ANS[i-D] + abs(A[i][0] - A[i-D][0]) + abs(A[i][1] - A[i-D][1])

for _ in range(Q):
    L, R = map(int, input().split())
    print(ANS[R] - ANS[L])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 2:
        print(a[0], a[1])
    ma = max(a)
    for i in range(n):
        if ma // 2 - i in a:
            print(ma, ma // 2 - i)
            exit()
        if ma // 2 - i + 1 in a:
            print(ma, ma // 2 - i + 1)
            exit()


main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 2:
        print(max(a), min(a))
    else:
        ma = max(a)
        sa = sorted([(i, abs(ma // 2 - a[i]))
                     for i in range(n)], key=lambda x: x[1])
        print(ma, a[sa[0][0]])


main()
### BUGGY CODE ###

k = int(input())
sevens = ['7']
result = -1
if not k % 2 == 0 and not k % 5 == 0:
    for i, _ in enumerate(range(k), 1):
        val = int(''.join(sevens))
        if val % k == 0:
            result = i
            break
        else:
            sevens.append('7')
print(result)  

### FIXED CODE ###

k = int(input())
target = 7; ans = -1
if not k % 2== 0:
    
    for i in range(1, k + 10):
        if target % k == 0:
            ans = i
            break
        target = (target * 10 + 7) % k
 
print(ans)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if b<n:
    n=b
for i in range(1,n+1):
    if i<b:
        s=math.floor(a*i/b)
    else:
        p=i//b
        q=i/b-p
        z=q*a
        s=math.floor(z)
    if s>max:
        max=s
print(int(max))


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    

print(max)