CodeEff/ECCO huggingface dataset:
# Original solution
import bisect


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    if N == 1:
        print(((monsters[0][1] + A - 1) // A))
        return
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

# Optimized solution
import bisect


def main():
    N, D, A = list(map(int, input().split()))
    monsters = [list(map(int, input().split())) for _ in range(N)]
    monsters.sort()
    X = [m[0] for m in monsters]
    # 端から貪欲に攻撃していく
    ans = 0
    damages = [0] * (N + 1)
    for n, monster in enumerate(monsters):
        x, h = monster
        h = max(0, h - damages[n])
        to_n = bisect.bisect_right(X, x + 2 * D)
        cnt = (h + A - 1) // A  # ceil(h / A)
        ans += cnt
        damages[n] += A * cnt
        damages[to_n] -= A * cnt
        damages[n + 1] += damages[n]
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
from heapq import heapify, heappop, heappush
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: tuple(map(int,input().split()))
N, D, A = inpl()
q = []
for _ in range(N):
    x, h = inpl()
    q.append((x, 0, h))
heapify(q)
ans = 0
d = 0
while q:
    x, s, h = heappop(q)
    if s == 0:
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            heappush(q, (x+2*D, 1, k*A))
            d += k*A
            ans += k
    else:
        d -= h
print(ans)

# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
Xmax = 10**10
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
XH.append([Xmax,0])
ans = 0
d = 0
i = j = 0
R = []
while True:
    if j >= len(R) or XH[i][0] <= R[j][0]:
        x, h = XH[i]
        i += 1
        if x >= Xmax:
            break
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            R.append((x+2*D, k*A))
            d += k*A
            ans += k
    else:
        x, h = R[j]
        j += 1
        d -= h
print(ans)
# Original solution
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print((bomb_ruisekiwa[-1]))

# Optimized solution
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
# bisectより尺取り法のほうが圧倒的に速いだろjk
bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print((bomb_ruisekiwa[-1]))
# Original solution
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print((bomb_ruisekiwa[-1]))


# Optimized solution
import math
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [math.ceil(xh[i][1]/a) for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
# bisectより尺取り法のほうが速いと思ったんだけど…
bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = h[i]
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = bomb_ruisekiwa[i-1]
        else:
            damage = bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]
        if h[i] - damage > 0:
            bomb = h[i] - damage
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print((bomb_ruisekiwa[-1]))
# Original solution
import math
import bisect
n,d,a = list(map(int,input().split()))
L = []
kyo = []
s = 0
for i in range(n):
    x,h = list(map(int,input().split()))
    L.append([x,h])
    kyo.append(x)
    s += h
L.sort()
kyo.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        times = int(math.ceil(L[temp][1]/a))
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        k = bisect.bisect_right(kyo, ran)
        next = temp+1
        for i in range(temp+1, k):
            if L[i][1] > damage:
                L[i][1] -= damage
                s -= damage
                next = min(next, i)
            else:
                s -= L[i][1]
                L[i][1] = 0
        temp = next
    else:
        for i in range(temp+1, n):
            if L[i] != 0:
                temp = i
                break
print(ans)


# Optimized solution
import math
import bisect
n,d,a = list(map(int,input().split()))
L = []
kyo = []
for i in range(n):
    x,h = list(map(int,input().split()))
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)
# Original solution
N,D,A=list(map(int,input().split()))
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in list(damage.items()):
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
        if X[i][1]<=0:
          break
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)


# Optimized solution
N,D,A=list(map(int,input().split()))
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
# lastX=X[-1][0] # 最後のモンスターの場所
damage=0 # 現在の爆発が与えられるダメージ
from collections import deque
bombs=deque() # 爆弾が切れるタイミング
# [位置、効力]
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1] # モンスターの体力
  # 爆発が途切れていないかを確認
  while bombs:
    b=bombs.popleft()
    if b[0]<x:
      damage-=b[1]
    else:
      bombs.appendleft(b)
      break
  h-=damage
  if h>0:
    turn=((h+A-1)//A)
    damage+=turn*A
    ans+=turn
    bombs.append([x+D,turn*A])
print(ans)
# Original solution
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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

XH = []

for i in range(N):

    x,h = list(map(int,input().split()))
    XH.append([x,h])

XH.sort()

q = deque([])
qs = 0
ans = 0

for i in range(N):

    X = XH[i][0]
    H = XH[i][1]

 
    while len(q) > 0 and q[0][0] < X-D:
        po = q.popleft()
        qs -= po[1] * A

    if H - qs <= 0:
        continue
        
    else:
        pl = updiv(H-qs,A)
        qs += pl * A
        ans += pl
        q.append([X+D,pl])

print (ans)
        


# Optimized solution
import bisect
from collections import deque
import math
n, d, A = list(map(int, input().split()))
xh = []
for _ in range(n):
    x, h = list(map(int, input().split()))
    xh.append([x, h])
xh.sort(key=lambda x: x[0])

monster_x = []
monster_hp = []
for i in range(n):
    monster_x.append(xh[i][0])
    monster_hp.append(xh[i][1])

dist = 2 * d
ans = 0
damage = 0
cum_damage = [0] * (n + 1)
for i in range(n):
    cum_damage[i + 1] += cum_damage[i]
    damage = cum_damage[i + 1] * A
    if damage < monster_hp[i]:
        min_attack_num = math.ceil((monster_hp[i] - damage) / A) 
        index = bisect.bisect_right(monster_x, monster_x[i] + dist)
        cum_damage[i + 1] += min_attack_num
        if index < n:
            t = min(index + 1, n)
            cum_damage[t] -= min_attack_num
        ans += min_attack_num

print(ans)
# Original solution
from collections import deque
N, D, A = list(map(int, input().split()))

ys = []
hs = []
for i in range(N):
    X, H = list(map(int, input().split()))
    ys.append((X,-(-H//A)))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = dmg = r = 0
hs2 = [0]*N
for i, (y, h) in enumerate(ys):
    while l < y:
        dmg -= hs2[li]
        li += 1
        l = ys[li][0] + 2*D
    hs2[i] = max(0, h-dmg)
    dmg += hs2[i]
    r += hs2[i]
print(r)


# Optimized solution
N, D, A = list(map(int, input().split()))
ys = []
for i in range(N):
    X, H = list(map(int, input().split()))
    ys.append((X,-(-H//A)))
ys.sort(key=lambda x : x[0])
li = dmg = r = 0
hs = [0]*N
for i, (y, h) in enumerate(ys):
    while ys[li][0]+2*D < y:
        dmg -= hs[li]
        li += 1
    hs[i] = max(0, h-dmg)
    dmg += hs[i]
    r += hs[i]
print(r)
# Original solution
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = list(map(int, read().split()))
X = XH[::2]
H = XH[1::2]
D *= 2
X, H = list(zip(*sorted(zip(X, H))))

damage = [0] * (N + 1)
answer = H[0] // A + min(1, H[0] % A)
damage[0] += A * answer
damage[bisect_right(X, X[0] + D)] -= A * answer

for i in range(1, N):
    damage[i] += damage[i - 1]
    h = H[i]
    x = X[i]
    if damage[i] >= h:
        continue
    else:
        h -= damage[i]

    cnt = h // A + min(1, h % A)
    answer += cnt
    damage[i] += A * cnt
    damage[bisect_right(X, x + D)] -= A * cnt

print(answer)


# Optimized solution
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = list(map(int, read().split()))
X = XH[::2] + [-1]
H = XH[1::2] + [-1]
D *= 2
X, H = list(zip(*sorted(zip(X, H))))

damages = [0] * (N + 2)
answer = 0

for i in range(1, N + 1):
    damages[i] += damages[i - 1]
    h = H[i]
    if damages[i] >= h:
        continue
    else:
        h -= damages[i]

    x = X[i]
    cnt = (h + A - 1) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D)] -= damage

print(answer)
# Original solution
from math import ceil
from collections import deque

N, D, A = list(map(int, input().split()))
monsters = []
for i in range(N):
    x, h = list(map(int, input().split()))
    monsters.append((x, h))
monsters.sort()

damege_sum = 0
ans = 0
q = deque([])
for i in range(N):
    x, h = monsters[i]
    while q and q[0][0] < x:
        damege_sum -= q[0][1]
        q.popleft()
    h -= damege_sum
    if h > 0:
        hit = ceil(h / A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)




# Optimized solution
from math import ceil
from collections import deque


N, D, A = list(map(int, input().split()))
monsters = []
for i in range(N):
    x, h = list(map(int, input().split()))
    monsters.append((x, h))
monsters.sort()


damage_sum = 0
ans = 0
q = deque([])
for i in range(N):
    x, h = monsters[i]
    while q and q[0][0] < x:
        damage_sum -= q[0][1]
        q.popleft()
    h -= damage_sum
    if h > 0:
        hit = ceil(h / A)
        ans += hit
        damage = hit * A
        damage_sum += damage
        q.append((x + 2 * D, damage))

print(ans)
# Original solution
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('f1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(eval(input()))


def read_str_list():
    return input().split()


def read_str():
    return eval(input())


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = list(map(list, list(zip(*pairs))))

    res = 0
    damage = 0
    q = []
    for i in range(n):
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.pop(0)
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import socket
from collections import deque


if socket.gethostname() in ['N551J', 'F551C']:
    in_file = 'f1.in'
    in_file = 'after_contest_01.in'
    sys.stdin = open(in_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(eval(input()))


def read_str_list():
    return input().split()


def read_str():
    return eval(input())


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = list(map(list, list(zip(*pairs))))

    res = 0
    damage = 0
    q = deque()
    for i in range(n):
        # print(i, damage, file=sys.stderr)
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.popleft()
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()
# Original solution
import bisect
import math
n,d,a=list(map(int,input().split()))
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    #print(h)
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            h[i]-=m*a
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)


# Optimized solution
import bisect
import math
import sys
input=sys.stdin.readline
n,d,a=list(map(int,input().split()))
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)
# Original solution
n, d, a = list(map(int, input().split()))
XH = []
for i in range(n):
    x, h = list(map(int, input().split()))
    XH.append((x, h))
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
# n, d, a = 9, 2, 2
# X = [1, 3, 4, 6, 9, 10, 12, 13, 16]
# H = [7, 6, 7, 5, 10, 3, 8, 9, 6]
X.append(10**10)
H.append(0)
j = 0
c = 0
S = [0]*(n+1)
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + -(-H[i]//a)*a
    S[j] -= -(-H[i]//a)*a
    # print(i)
    # print(H)
    # print(S)
# print(H)
# print(S)
print(c)


# Optimized solution
n, d, a = list(map(int, input().split()))
XH = [tuple(map(int, input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)
# Original solution
k,n=list(map(int,input().split()))
l1=list(map(int,input().split()))
l2 = [x+k for x in l1]
l=l1+l2
ans=[]
for i in range(n):
    ans.append(max(l[i+1:i+n])-l[i] )
print((min(ans)))

# Optimized solution
k,n,*a=list(map(int,open(0).read().split()))
a+=[k+a[0]]
print((k-max(y-x for x,y in zip(a,a[1:]))))
# Original solution
inputted = list(map(int, input().split()))
K = inputted[0]
N = inputted[1]
A = list(map(int, input().split()))

distancies = []
for i, Ai in enumerate(A):
    current = i
    to = (i + 1) % len(A)
    distance = A[to] - A[current] if i < len(A) - 1 else K - A[current] + A[0]
    distancies.append(distance)

answer = K - max(distancies)

print(answer)


# Optimized solution
inputted = list(map(int, input().split()))
K = inputted[0]
N = inputted[1]
A = list(map(int, input().split()))

distancies = []
for i, Ai in enumerate(A):
    current = i
    to = (i + 1) % len(A)
    distance = A[to] - A[current] if to != 0 else K - A[current] + A[0]
    distancies.append(distance)

answer = K - max(distancies)

print(answer)
# Original solution
k,n = list(map(int,input().split()))
A = list(map(int,input().split()))

for i in range(n-1):
    for j in range(n-1-i):
        if A[j] > A[j+1]:
            A[j],A[j+1] = A[j+1],A[j]


max_d = 0
max_index = 0
for i in range(n-1):
    if A[i+1] - A[i] > max_d:
        max_d = A[i+1]-A[i]
        max_index = i

if k-A[n-1]+A[0] > max_d:
    max_d = k-A[n-1]+A[0]
    max_index = n-1

min_distance = 0

if(max_index != n-1):
    min_distance = A[max_index]+k-A[max_index+1]
else:
    min_distance = A[n-1]-A[0]

print(min_distance)


# Optimized solution
k,n = list(map(int,input().split()))
A = list(map(int,input().split()))


max_d = 0
max_index = 0
for i in range(n-1):
    if A[i+1] - A[i] > max_d:
        max_d = A[i+1]-A[i]
        max_index = i

if k-A[n-1]+A[0] > max_d:
    max_d = k-A[n-1]+A[0]
    max_index = n-1

min_distance = 0

if(max_index != n-1):
    min_distance = A[max_index]+k-A[max_index+1]
else:
    min_distance = A[n-1]-A[0]

print(min_distance)
# Original solution
K, N = list(map(int, input().split()))
house = list(map(int,input().split()))
house = house + house
min = house[N - 1] - house[0]
 
for i in range(N - 1):
  if K - (house[N + 1 + i] - house[i]) < min:
    min = K - (house[N + 1 + i] - house[i])
 
print(min)

# Optimized solution
K, N = list(map(int, input().split()))
house = list(map(int,input().split()))
min = house[N - 1] - house[0]
 
for i in range(N - 1):
  if K - (house[i + 1] - house[i]) < min:
    min = K - (house[i + 1] - house[i])
 
print(min)
# Original solution
K, N = list(map(int, input().split()))
As = list(map(int, input().split()))
Ds = []
past = 0
for i, a in enumerate(As):
    if not i==0:
        Ds.append(a-past)
    past = a
Ds.append(As[0]+K-As[-1])
print((K-max(Ds)))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

K, N = mapint()
As = list(mapint())

lis = []
for i in range(1, N):
    lis.append(As[i]-As[i-1])
lis.append(As[0]+(K-As[-1]))
print((K-max(lis)))
# Original solution

from os import readlink


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

ans = K - (X[0] + K - X[-1])
for i in range(1, N):
    ans = min(ans, K - (X[i] - X[i - 1]))
print(ans)


# Optimized solution

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

ans = K + X[0] - X[-1]
for i in range(1, N):
    ans = max(ans, X[i] - X[i - 1])
print((K - ans))
# Original solution
import sys
input = sys.stdin.readline


def main():
    K, N = list(map(int, input().split()))
    A = list(map(int, input().split()))
    diff = []
    for i in range(N-1):
        diff.append(A[i+1] - A[i])
    diff.append(A[0]+K-A[N-1])
    print((sum(diff)-max(diff)))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
input = sys.stdin.readline


def main():
    K, N = list(map(int, input().split()))
    A = list(map(int, input().split()))
    diff = [A[i+1] - A[i] for i in range(N-1)]
    diff.append(A[0]+K-A[N-1])
    print((sum(diff)-max(diff)))


if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

def main():
    k, n = list(map(int, input().split()))
    a = list(map(int, input().split()))
    longest = a[0] + k - a[-1]
    for i in range(n - 1):
        longest = max(longest, a[i+1] - a[i])

    print((k - longest))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
read = sys.stdin.read
def main():
    k, n = list(map(int, input().split()))
    a = tuple(map(int, input().split()))
    dis_max = (k - a[-1]) + a[0]
    for i1 in range(1, n):
        dis = a[i1] - a[i1-1]
        dis_max = max(dis_max, dis)
    print((k - dis_max))
if __name__ == '__main__':
    main()