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

import numpy as np
n, d, a = (int(x) for x in input().split())
xh = np.empty((0, 2))
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh = np.vstack((xh, np.array([x, h])))
xh = xh[np.argsort(xh[:, 0])]
cnt = 0
while True:
    if xh[xh[:, 1] > 0].size == 0:
        break
    xx, hh = xh[(xh[:, 1] > 0)][0]
    num = hh // a
    if hh % a != 0:
        num += 1
    xh[(xh[:, 0] >= xx) & (xh[:, 0] <= xx + 2 * d), 1] -= num * a
    cnt += num
print(int(cnt))

### FIXED CODE ###

from math import ceil
from bisect import bisect_right
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)
### BUGGY CODE ###

# -*- coding: UTF-8 -*-
# ABC066_C

N = int(input())
tmp = input()
list = []
list = tmp.split()

ans = []
if (N % 2 == 0):
    for i in range(1, N + 1):
        x = list[i - 1]
        if (i % 2 != 0):
            ans.append(x)
        else:
            ans.insert(0, x)
else:
    for i in range(1, N + 1):
        x = list[i - 1]
        if (i % 2 != 0):
            ans.insert(0, x)
        else:
            ans.append(x)
for i in range(0, N):
    print(ans[i], end=" ")


### FIXED CODE ###

# -*- coding: UTF-8 -*-
# ABC066_C

N = int(input())
tmp = input()
list = []
list = tmp.split()

if (N % 2 == 0):
    for i in range(N - 1, -1, -2):
        print(list[i], end=" ")
    for i in range(0, N, 2):
        print(list[i], end=" ")
else:
    for i in range(N - 1, -1, -2):
        print(list[i], end=" ")
    for i in range(1, N, 2):
        print(list[i], end=" ")
### BUGGY CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]

for _ in range(n-1):
  a,b = map(int, input().split())
  Tree[a].append(b)
  Tree[b].append(a)
  
for _ in range(q):
  p,x = map(int, input().split())
  Counter[p] += x

P = [-1 for _ in range(n+1)]  

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

### FIXED CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop()
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])
### BUGGY CODE ###

#XORはビットごとに独立しているので各ビットで0*1の演算回数を数える
n=int(input())
A=list(map(int,input().split()))
B=[0]*62 #1の個数カウント
mod=10**9+7

for i in range(n):
    a=bin(A[i])[2:]
    for j in range(len(a)):
        if a[-j-1]=="1":
            B[-j-1]+=1
ans=0
cnt=1 #2の累乗管理
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)

### FIXED CODE ###

#XORはビットごとに独立しているので各ビットで0*1の演算回数を数える
n=int(input())
A=list(map(int,input().split()))
B=[0]*62 #1の個数カウント
mod=10**9+7

for i in range(n):
    a=bin(A[i])
    for j in range(len(a)-2):
        if a[-j-1]=="1":
            B[-j-1]+=1

ans=0
cnt=1 #2の累乗管理
for b in range(len(B)):
    prd=B[-b-1]*(n-B[-b-1])
    ans+=prd*cnt%mod
    cnt*=2
    ans%=mod
    cnt%=mod
print(ans)
### BUGGY CODE ###

from decimal import *
getcontext().prec = 100000

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

if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from decimal import *
getcontext().prec = 28

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

if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')
### BUGGY CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s = []

    for i in range(N):
        sorted_s.append(sorted(s[i]))
        
    for i in range(N):
        # sorted_si = sorted(s[i])

        for j in range(i + 1, len(s)):
            # sorted_sj = sorted(s[j])

            if sorted_s[i] == sorted_s[j]:
            # if sorted_si == sorted_sj:
                anagram_num += 1

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))


### FIXED CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s_sub = []
    sorted_s = []
        
    for i in range(N):
        sorted_si = sorted(s[i])
        sorted_s_sub.append(''.join(sorted_si))

    sorted_s = sorted(sorted_s_sub)

    i = 0
    item_count = []
    while i < N:
        item = sorted_s[i]
        j = i + 1
        count = 1
        while j < N:
            if item == sorted_s[j]:
                count += 1
                j += 1
            else:
                break
        item_count.append(count)
        i += count  # count だけ進める
    
    for count in item_count:
        
        anagram_num += int(count * (count - 1) / 2)

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
ans = 0
for i in range(n):
    l = a[:]
    l.pop(i)
    print(max(l))

### FIXED CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
l = a[:]
l.sort(reverse=True)
x = l[0]
y = l[1]
ans = 0
for i in range(n):
    if a[i] == x:
        ans = y
    else:
        ans = x
    print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    s1 = input()
    S.append(s1)

ans = 1
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        cnt = 1
        for dy, dx in d:
            y = i + dy
            x = j + dx
            while 0 <= y < H and 0 <= x < W and S[y][x] == ".":
                cnt += 1
                y += dy
                x += dx
        ans = max(ans, cnt)

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    s1 = input()
    S.append(s1)

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
for i in range(W):
    if S[0][i] == ".":
        U[0][i] = 1
    if S[H-1][i] == ".":
        D[H-1][i] = 1

for i in range(H):
    if S[i][0] == ".":
        L[i][0] = 1
    if S[i][W-1] == ".":
        R[i][W-1] = 1
     
for i in range(1,H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        U[i][j] = U[i-1][j] + 1
for i in range(H-1)[::-1]:
    for j in range(W):
        if S[i][j] == "#":
            continue
        D[i][j] = D[i+1][j] + 1
for i in range(H):
    for j in range(1,W):
        if S[i][j] == "#":
            continue
        L[i][j] = L[i][j-1] + 1
for i in range(H):
    for j in range(W-1)[::-1]:
        if S[i][j] == "#":
            continue
        R[i][j] = R[i][j+1] + 1
        
ans = 0

for i in range(H):
    for j in range(W):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
print(ans)
### BUGGY CODE ###

n,g = map(int,input().split())
lis = []
mon = []
for i in range(n):
  a,b = map(int,input().split())
  lis.append([a,b])
score = {(0,0)}
for i in range(n):
  gone = set()
  for nu,cou in score:
    for j in range(lis[i][0]+1):
      if j != lis[i][0]:
        gone.add((nu+(i+1) * 100 * j,cou + j))
      else:
        gone.add((nu+(i+1) * 100 * j + lis[i][1],cou + j))
  score = gone
ans = 10 ** 12
for nu,num in score:
  if nu >= g:
    ans = min(ans,num)
print(ans)


### FIXED CODE ###

import math
n,g = map(int,input().split())
lis = []
sum = []
for i in range(n):
  a,b = map(int,input().split())
  lis.append([a,b])
  sum.append((i+1)*100*a+b)
def ans(x,y):
  if y <= 0:return 10 ** 12
  nu = min(math.ceil(x/(100 * y)),lis[y-1][0])
  num = 100 * y * nu
  if nu == lis[y-1][0]:num += lis[y-1][1]
  if num >= x:cou = nu
  else:cou = nu +ans(x-num,y-1)
  return min(cou,ans(x,y-1))

print(ans(g,n))
### BUGGY CODE ###

import time

h, n = map(int, input().split())

INF = 10 ** 20


dp = [INF for i in range(h + 10**4)]
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):

    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)


### FIXED CODE ###

def main():
    inf = 10**9
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))
 
 
main()
### BUGGY CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
S = S()
ans = 0
while 1:
    if S.count('BW')==0:
        break
    ans += S.count('BW')
    S = S.replace('BW','WB')
print(ans)


### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
S = S()
ans,target_index = 0,0
for i in range(len(S)):
    if S[i]=='W':
        ans += i-target_index
        target_index += 1
print(ans)
### BUGGY CODE ###

S = list(input())
T = list(input())

ans = True 

while S != []:
    lis = []
    lit = []
    x = S[0]
    y = T[0]
    for i in range(len(S)):
        if x == S[i]:
            lis.append(i)
        if y == T[i]:
            lit.append(i)
    if lis == lit:
        while x in S:
            S.remove(x)
        while y in T:
            T.remove(y)
        continue
    else:
        ans = False
        break
if ans:
    print('Yes')
if not ans:
    print('No')

### FIXED CODE ###

Sp = list(input())
Tp = list(input())
S = [ord(Sp[i])-ord('a') for i in range(len(Sp))]
T = [ord(Tp[i])-ord('a') for i in range(len(Tp))]
lis = [-1]*26
lit = [-1]*26
ans = True
for i in range(len(S)):
    if lis[S[i]] == -1:
        lis[S[i]] = T[i]
    else:
        if lis[S[i]] != T[i]:
            ans = False
            break
for i in range(len(T)):    
    if lit[T[i]] == -1:
        lit[T[i]] = S[i]
    else:
        if lit[T[i]] != S[i]:
            ans = False
            break
if ans:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[1:])["E"]]
th = Counter(st[:n])["W"]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
    if(th-(n-i) > min(ma)):
        break
print(min(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

while 1:
 n=int(input())
 if n:
  a=[int(input())for _ in[0]*n]
  print(max([sum(a[i:j+1])for i in range(n)for j in range(i,n)]))


### FIXED CODE ###

while 1:
 n=int(input())
 if n==0:break
 a=[int(input())for _ in[0]*n]
 for i in range(1,n):a[i]=max(a[i],a[i]+a[i-1])
 print(max(a))
### BUGGY CODE ###

import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]

a=[]    
for i in range(n):
  a.append([s.index(i)+1  for i in list(input())])

aa_cij=np.array(a)
z=np.zeros((n,n))
ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  for j in range(n):
    aa_cij=np.concatenate( [ aa_cij[:,1:], aa_cij[:,[0]] ], axis=1)

    #print(aa_cij)
    #print(aa_cij.T)
    #print(np.diag(np.diag(at)))
    #print(at-np.diag(np.diag(at)))
    if np.allclose(aa_cij-aa_cij.T,z):
      ans+=1 
print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]
 
aa_cij=np.array([[s.index(i)+1  for i in list(input())] for _ in range(n)],dtype='int8')
z=np.zeros((n,n),dtype='int8')
ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  if np.allclose(aa_cij - aa_cij.T, z ):
    ans+=1 
print(ans*n)
### BUGGY CODE ###

n,m = map(int,input().split())
dp = [float('inf')]*(1<<n)
dp[0] = 0
for _ in range(m):
    a,b = map(int,input().split())
    bit = 0
    for e in map(int,input().split()):
        bit += 1<<(e-1)
    for i in range(1<<n):
        dp[i|bit] = min(dp[i|bit], dp[i]+a)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
dp = [float('inf')]*(1<<n)
dp[0] = 0
for _ in range(m):
    a,b = map(int,input().split())
    bit = 0
    for e in map(int,input().split()):
        bit += 1<<(e-1)
    for i in range(1<<n):
        dp[i|bit] = min(dp[i|bit], dp[i]+a)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

mod = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 0
dp = [0 for _ in range(n+1)]
dp[0] = 1
for i in range(n):
    dp[i] %= mod
    if i in a:
        continue
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
broken = [False] * (n + 1)
for i in range(m):
    a = int(input())
    broken[a] = True
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % MOD)
### BUGGY CODE ###

def f(X,A):
    temp_f = [X^A[i] for i in range(len(A))]
    return sum(temp_f)
def calc_max_f(A,K):
    temp_max_f = [f(k,A) for k in range(0,K+1)]
    return max(temp_max_f)
N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
print(calc_max_f(A,K))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)
### BUGGY CODE ###

import collections

S = input()

mod_list = [0]+[False for i in range(len(S))]

for i in range(len(S)):
    index = len(S) - i - 1
    
    num = int(S[index:])
    mod_list[i+1] = num % 2019


CTR_mod_list = collections.Counter(mod_list).most_common()
cnt = 0

for i in range(len(CTR_mod_list)):
    n = CTR_mod_list[i][1]

    if (n > 1):
        cnt += n * (n - 1) // 2

print(cnt)


### FIXED CODE ###

def main():
    import collections

    S = input()

    mod_list = [0]

    for i in range(len(S)):
        index = len(S) - i - 1
        num = int(S[index])

        mod_list.append((mod_list[-1] + num * pow(10, i, 2019)) % 2019)

    CTR_mod_list = collections.Counter(mod_list).most_common()
    cnt = 0

    for i in range(len(CTR_mod_list)):
        n = CTR_mod_list[i][1]

        if (n == 1):
            break

        cnt += n * (n - 1) // 2

    print(cnt)

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

class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF = UnionFind(2*n)
    for i in range(k):
        p,q = map(int,input().split())
        UF.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF.unite(n+r-1,n+s-1)

    for i in range(n):
        res = 0
        for j in range(n):
            if UF.same(i,j) and UF.same(i+n,j+n):
                res += 1
        print(res,end=' ')
    



### FIXED CODE ###

import bisect
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = {}

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    l = []
    dic = {}
    for i in range(n):
        tmp = (UF_k.find(i),UF_l.find(i))
        l.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for fac in l:
        print(dic[fac],end=' ')
### BUGGY CODE ###

from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor
import numpy as np
from collections import defaultdict, deque,Counter
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n, m, q = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(q)]
    ans = 0
    for i in range(2 ** q):  # とるかとらないかの2択
        check = [0] * q
        for j in range(q):
            if i >> j & 1:
                check[j] = 1
        # print(check)
        A = [1] * n
        used = [0] * n
        tmp = 0
        for k in range(q):
            if check[k]:  # とる時
                a, b, c, d = l[k]
                a -= 1
                b -= 1
                if not used[b]:  # 使ってない時は変更できる
                    A[b] = c + A[a]
                    tmp += d
                    used[b] = 1  # 変更ずみにする
                    used[a] = 1
                elif A[b] == c + A[a]:  # たまたま変更してからあってたら追加
                    tmp += d
                else:  # 条件に合わない場合
                    tmp = 0
                    break
        if max(A) > m:  # Aの最大値がm以下である
            tmp = 0
        ans = max(ans, tmp)
    print(ans)





if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import permutations, accumulate, combinations, combinations_with_replacement
import sys
input = sys.stdin.readline


def main():
    n, m, q = map(int, input().split())
    # <方針>：Aを全列挙する
    ans = 0
    a = [0] * q
    b = [0] * q
    c = [0] * q
    d = [0] * q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
    for A in combinations_with_replacement(range(1, m + 1), n):
        tmp = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp += d[i]
        ans = max(ans, tmp)
    print(ans)


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

n,m=input().split()
n=int(n)
m=int(m)
i=0
x=list()
ans=0



while m!=i:
    i=i+1
    l,r=input().split()
    l=int(l)
    r=int(r)
    while l != r + 1:
        x.append(l)
        l = l + 1
i=0
while n+1!=i:
    i=i+1
    if x.count(i)==m:
        ans=ans+1
print(ans)



### FIXED CODE ###

n,m=input().split()
n=int(n)
m=int(m)
i=0
x=list()
y=list()
ans=0
g=0
ll=[]
rr=[]


while i!=m:
    i=i+1
    l,r=input().split()
    l=int(l)
    r=int(r)
    ll.append(l)
    rr.append(r)
l=max(ll)
r=min(rr)

ans=r-l+1
if l>r:
    ans=0
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
a=[i for i in a if i in b]
p=list(set(b))
c=0
for i in range(len(p)):
    if b.count(p[i])>a.count(p[i]):
        c=1
print("YES"if c!=1else"NO")

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a=Counter(a)
m=int(input())
b=list(map(int,input().split()))
b=Counter(b)
for d,e in b.items():
    if a[d]<e:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N = int(input())
S = input()


def z_algorithm(s):
    n = len(s)
    lcpls = [0] * n  # Longest common prefix length
    lcpls[0] = n

    l = r = 1
    while l < n:
        while (r < n) and (s[r - l] == s[r]):
            r += 1

        if l == r:
            l += 1
            r += 1
            continue

        lcpls[l] = r - l

        k = 1
        while (l + k < r) and (lcpls[k] < r - l - k):
            lcpls[l + k] = lcpls[k]
            k += 1
        l += k

    return lcpls


ans = 0
for i in range(N):
    X = S[i:]
    Z = z_algorithm(X)

    for j, z in enumerate(Z):
        if j >= z:
            ans = max(ans, z)

print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


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

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = np.full(N, int(1e15))

    dp[0] = 0
    for i in range(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)
    print(int(dp[N-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    h = np.array(list(map(int, input().split())))
    dp = np.zeros(N, dtype=int)

    dp[0] = 0
    for i in range(1, N):
        start = max(0, i - K)
        dp[i] = min(dp[start:i] + np.abs(h[start:i] - h[i]))
    # print(dp)
    print(int(dp[N-1]))

if __name__ == "__main__":
    main()