Harryxun/stf_run huggingface dataset:
n,m=map(int,input().split())
l=[[]for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    l[x].append(y)

memo=[0]*(n+1)
def chain(v):
    if memo[v]!=0:
        return memo[v]
    else:
        for a in l[v]:
            memo[v]=max(chain(a)+1,memo[v])
        return memo[v]
res=0
for i in range(1,n+1):
    res=max(res,chain(i))
print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
l=[[]for _ in range(n+1)]
for _ in range(m):
    x,y=map(int,input().split())
    l[x].append(y)

memo=[0]*(n+1)
def chain(v):
    if memo[v]!=0:
        return memo[v]
    else:
        for a in l[v]:
            memo[v]=max(chain(a)+1,memo[v])
        return memo[v]
res=0
for i in range(1,n+1):
    res=max(res,chain(i))
print(res)
import itertools
import numpy as np
def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))

    x = [sum(a[i:j+1]) for i in range(n) for j in range(i,n)]
    x.sort()
    x = x[::-1]
    ans = []
    for ls in itertools.combinations(range(k**2), k):
        y = x[ls[0]]
        for i in ls[1:]:
            y = y & x[i]
        ans.append(y)
    print(max(ans))
    # for i in range(k-1):
    #     ans = ans & x[i+1]
    # print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
import numpy as np
def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))

    x = [sum(a[i:j+1]) for i in range(n) for j in range(i,n)]
    x.sort()
    x = x[::-1]

    MAX = x[0]
    two = 1
    POW = 1
    while(MAX>=two*2):
        two*=2
        POW+=1

#MAXBITソート
    for p in range(POW)[::-1]:
        C = list(filter(lambda y:y>=two,x))
        if len(C)>=k:
            break
        else:
            two//=2

    POW = p+1

    for p in range(POW):
        D = list(filter(lambda x:(x//two)%2==1,C))
        LEN = len(D)
        if LEN>=k:
            C = D[:]
            if LEN==k:break
        two//=2

    ans = C[0]
    for c in C[1:k]:
        ans &= c

    print(ans)

if __name__ == "__main__":
    main()
def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    maxv = 0
    acum = [0] * (n + 1)
    bcum = [0] * (m + 1)
    for i in range(n):
        acum[i + 1] = acum[i] + a[i]
    for i in range(m):
        bcum[i + 1] = bcum[i] + b[i]

    for i in range(n + 1):
        if acum[i] > k:
            continue
        maxv = max(maxv, i + bisect_right(bcum, k - acum[i]) - 1)
    print(maxv)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    acum = [0] * (n + 1)
    bcum = [0] * (m + 1)
    for i in range(n):
        acum[i + 1] = acum[i] + a[i]
    for i in range(m):
        bcum[i + 1] = bcum[i] + b[i]
        
    j = m
    maxv = 0
    for i in range(n+1):
        if acum[i] > k:
            break
        while acum[i] + bcum[j] > k:
            j -= 1
        maxv = max(maxv, i + j)
    print(maxv)

if __name__ == '__main__':
    main()
a, b = map(int, input().split())

import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))


### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

print(lcm(a, b))
from itertools import count

for i in count(1):
    if i == 10:
        break
    else:
        print("Case {}: {}".format(i, s))

### FIXED CODE ###

from itertools import count

for i in count(1):
    s = input()

    if s == "0":
        break
    else:
        print("Case {}: {}".format(i, s))
N, K = map(int, input().split())
n_1 = N - (K * (N // K))
n_2 = abs(n - K)
print(min(n_1, n_2))

### FIXED CODE ###

N, K = map(int, input().split())
n_1 = N - (K * (N // K))
n_2 = abs(n_1 - K)
print(min(n_1, n_2))
C = input()
print(chr(ord(c)+1))

### FIXED CODE ###

C = input()
print(chr(ord(C)+1))
N, K =map(int, input().split())
S = input()
S=list(S)
S[K] = S[K].lower()
print("".join(S))


### FIXED CODE ###

N, K =map(int, input().split())
S = input()
S=list(S)
S[K-1] = S[K-1].lower()
print("".join(S))
N,K,S=[int(i) for i in input().split()]
res=[10**9-1]*N
for i in range(K):
    res[i]=S
print(*res)

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


### FIXED CODE ###

N,K,S=[int(i) for i in input().split()]
res=[S%10**9+1]*N
for i in range(K):
    res[i]=S
print(*res)
from collections import defaultdict

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

D = defaultdict(set)
R = {}
for _ in range(M):
  a, b = map(int, input().split())
  if a in R:
    if b in R:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        if len(D[aa]) < len(D[bb]):
          aa, bb = bb, aa
        for x in D[bb]:
          R[x] = aa
        D[aa] |= D[bb]
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].add(b)
  else:
    if b in R:
      R[a] = R[b]
      D[R[b]].add(a)
    else:
      R[a] = a
      R[b] = a
      D[a].add(a)
      D[a].add(b)

print(max(len(x) for x in D.values()))

### FIXED CODE ###

from collections import defaultdict

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

D = defaultdict(set)
R = {}
for _ in range(M):
  a, b = map(int, input().split())
  if a in R:
    if b in R:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        if len(D[aa]) < len(D[bb]):
          aa, bb = bb, aa
        for x in D[bb]:
          R[x] = aa
        D[aa] |= D[bb]
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].add(b)
  else:
    if b in R:
      R[a] = R[b]
      D[R[b]].add(a)
    else:
      R[a] = a
      R[b] = a
      D[a].add(a)
      D[a].add(b)

print(max(len(x) for x in D.values()) if D else 1)
import numpy as np

def main():
    N = int(input())
    A, B, C = np.full((3,N),0)

    for i in range(N):
        A[i], B[i], C[i] = [int(x) for x in input().split()]

    DP = np.full((N,3),0,dtype=int)

    act = [A,B,C]

    for i, X in enumerate(act):
        DP[0][i] = X[0]
    
    for i in range(N-1):
        for x, X in enumerate(act):
            for y, Y in enumerate(act):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+Y[i+1])

    print(DP[-1].max())

if __name__ == "__main__":
    main()
    pass

### FIXED CODE ###

def main():
    N = int(input())
    DP = [[0 for i in range(3)] for j in range(N+1)]
    
    for i in range(N):
        a = list(map(int, input().split()))
        for x in range(3):
            for y in range(3):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+a[y])
    print(max(DP[-1]))

if __name__ == "__main__":
    main()
    pass
import collections
n = int(raw_input())
count = 0
cc= collections.Counter()
for i in range(1,n + 1):
	while(j <= n):
		cc[j] += 1
		j +=i
	if i % 2 and cc[i] == 8 :
		count +=1
print count

### FIXED CODE ###

import collections
n = int(raw_input())
count = 0
cc= collections.Counter()
for i in range(1,n + 1):
	j = i
	while(j <= n):
		cc[j] += 1
		j +=i
	if i % 2 and cc[i] == 8 :
		count +=1
print count
def main(argv):
    for v in argv:
        print(v)

main()

### FIXED CODE ###

def main(argv):
    for i in range(len(argv)):
        check = sum(argv[i] == argv[j] for j in range(len(argv)))
        if check != len(argv)-1:
            return argv[i]


argv = list(map(int, input().split()))
print(main(argv))
N, M = map(int,input().split())
A = list(map(int, input().split()))
line = sum(A)/(4*M)
A.sort(reverse=True)
if A[M]>line:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int, input().split()))
line = sum(A)/(4*M)
A.sort(reverse=True)
if A[M-1]>=line:
    print('Yes')
else:
    print('No')
import math
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(n):
    ans = math.gcd(ans, a[i])
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(n):
    ans = fractions.gcd(ans, a[i])
print(ans)
import math
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(n-2):
    g = math.gcd(g,a[i+2])
print(g)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
g = gcd(a[0],a[1])
for i in range(n-2):
    g = gcd(g,a[i+2])
print(g)
#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n-i) % MOD
        y *= i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()
atcoder-tools: The pre-rendered templates are not found.

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y =  map(int, readline().split())

if x < y:
    x, y = y, x

b = (2 * x - y) // 3 
if (2 * x - y) % 3  != 0:
    print(0)
    exit()

a = x - 2 * b

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 * 2 + 2
fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod
    
comInit(MOD)

print(com(a + b, b, MOD))

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y =  map(int, readline().split())

if x < y:
    x, y = y, x

b = (2 * x - y) // 3 
if (2 * x - y) % 3  != 0:
    print(0)
    exit()

a = x - 2 * b
if a < 0:
    print(0)
    exit()

MOD = 10 ** 9 + 7
a %= MOD
b %= MOD

MAX = 10 ** 6 * 2 + 2
fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod
    
comInit(MOD)
print(com(a + b, b, MOD))
num = input().split()
a, b =int(num[0]), int(num[1])

ans = sorted([a+b, a-b, a*b , a//b])

print(ans[-1])

### FIXED CODE ###

num = input().split()
a, b =int(num[0]), int(num[1])

ans = sorted([a+b, a-b, a*b])

print(ans[-1])
print(N)


### FIXED CODE ###

N = int(input())
print(round((N/2)+0.01))
N,K=map(int,input.split())
TMP=K
ANS=1
if N <= K:
  ANS=1
else:
  TMP=(K-1)
  ANS+=1
  if N <= K:
    break
print(ANS)


### FIXED CODE ###

N,K=map(int,input().split())
TMP=K
ANS=1
if N <= K:
  ANS=1
else:
  while True:
    TMP+=(K-1)
    ANS+=1
    if N <= TMP:
      break
print(ANS)
# input
N = int(input())
A = list(map(int, input().split()))

ans = 1

if N % 2 == 0:
    for i in range(1, N, 2):
        if A.count(i) > 2:
            print(0)
            exit()
    for i in range(N / 2):
        ans = (ans * 2) % (10 ^ 9 + 7)
    print(ans)
else:
    if A.count(0) > 1:
        print(0)
        exit()
    for i in range(2, N, 2):
        if A.count(i) > 2:
            print(0)
            exit()
    for i in range(N // 2):
        ans = (ans * 2) % (10 ^ 9 + 7)
    print(ans)

### FIXED CODE ###

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

cnt = [0 for i in range(N)]
ans = 1

if N % 2 == 0:
    for i in range(N):
        if A[i] % 2 == 0:
            print(0)
            exit()
        cnt[A[i]] += 1
        if cnt[A[i]] > 2:
            print(0)
            exit()
        if cnt[A[i]] == 1:
            ans = (ans * 2) % (10 ** 9 + 7)
    print(ans)
else:
    for i in range(N):
        if A[i] % 2 == 1:
            print(0)
            exit()
        if A[i] > 0:
            cnt[A[i]] += 1
            if cnt[A[i]] > 2:
                print(0)
                exit()
            if cnt[A[i]] == 1:
                ans = (ans * 2) % (10 ** 9 + 7)
        if A[i] == 0:
            cnt[0] += 1
            if cnt[0] > 1:
                print(0)
                exit()
    print(ans)
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*(((H*W-1)-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i-1][0]
    x2=A[D*(k+1)+i-1][0]
    y1=A[D*k+i-1][1]
    y2=A[D*(k+1)+i-1][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  if l!=l%D:
    ans=S[l%D][(r-l%D)//D]-S[l%D][(l-l%D)//D]
  else:
    ans=S[l%D][(r-l%D)//D]
  print(ans)
  ans=0

### FIXED CODE ###

H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0
import math
n = int(input())
t = [int(input()) for _ in range(n)]

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

ans = 1
for i in range(n):
    ans = lcm(t[i],ans)
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
t = [int(input()) for _ in range(n)]

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

ans = 1
for i in range(n):
    ans = lcm(t[i],ans)
print(ans)
A,B = map(int,input().split())
   ...:
   ...:
   ...: def kaibun(m, n):
   ...:     key = 0
   ...:     for i in range(m,n+1):
   ...:         s = i//10000
   ...:         t = i%10
   ...:         u = i//1000 % 10
   ...:         v = i//10 % 10
   ...:         if (s==t)&(u==v):
   ...:             key += 1
   ...:     return key
   ...:
   ...: print(kaibun(A,B))

### FIXED CODE ###

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


def kaibun(n):
	key = 0
	for i in range(1,n+1):
		if str(i) == str(i)[::-1]:
			key += 1
	return key

print(kaibun(B)-kaibun(A-1))
from decimal import *
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(a).sqrt(b)<Decimal(a).sqrt(c):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

from decimal import *
a,b,c=map(int,input().split())
if Decimal(a).sqrt()+Decimal(b).sqrt()<Decimal(c).sqrt():
  print("Yes")
else:
  print("No")
N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [[] for i in range(N)]

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

### FIXED CODE ###

import numpy as np

N,K = map(int, input().split())
h = np.array(list(map(int,input().split())))

dp = np.zeros(N, dtype = int)

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    P, M = [], []
    for a in A:
        P.append(a) if a >= 0 else M.append(a)

    res = 1
    if len(P) == n:
        A.sort(reverse=True)
        for i in range(k):
            res = (res * A[i]) % mod
    elif len(M) == n:
        if k % 2:
            A.sort(reverse=True)
        else:
            A.sort()
        res = 1
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort(reverse=True)
        M.sort()
        B = []
        if k % 2:
            k -= 1
            b = P.pop(0)
            res = (res * b) % mod
        for i in range(0, len(P), 2):
            if i + 1 < len(P):
                B.append(P[i] * P[i + 1])
        for j in range(0, len(M), 2):
            if j + 1 < len(M):
                B.append(M[j] * M[j + 1])
        B.sort(reverse=True)
        for i in range(k // 2):
            res = (res * B[i]) % mod

    print(res)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    M, P = [], []
    for a in A:
        M.append(a) if a < 0 else P.append(a)

    m, p = len(M), len(P)
    ok = False
    if p > 0:
        ok = m % 2 == 0 if n == k else True
    else:
        ok = k % 2 == 0

    res = 1
    if not ok:
        A.sort(key=lambda x: abs(x))
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort()
        M.sort(reverse=True)
        if k % 2:
            a = P.pop()
            res = (res * a) % mod
        M_2 = []
        while len(P) >= 2:
            a = P.pop()
            a *= P.pop()
            M_2.append(a)
        while len(M) >= 2:
            a = M.pop()
            a *= M.pop()
            M_2.append(a)
        M_2.sort(reverse=True)
        for i in range(k // 2):
            res = (res * M_2[i]) % mod
    print(res)


if __name__ == '__main__':
    resolve()
def test(array, index, last_position, count, min_count):
    if index + 1 == len(array):
        # print("count:{}".format(count))
        min_count[0] = count if min_count[0] == - \
            1 or count < min_count[0] else min_count[0]
        return
    current = array[index]
    next = array[index + 1]

    # 前か次のと手がぶつかる場合は取り除く
    if last_position >= current[0] - \
            current[1] or current[0] + current[1] >= next[0] - next[1]:
        test(array, index + 1, last_position, count + 1, min_count)
    # 前のとぶつからない場合は取り除かないパターンも
    if last_position < current[0] - current[1]:
        test(array, index + 1, index, count, min_count)


N = int(input())
array = sorted([list(map(int, input().split()))
                for i in range(N)], key=lambda x: x[0])
min_count = [-1]
test(array, 0, -1, 0, min_count)
print(len(array) - min_count[0])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


def test(array, index, last_position, count, min_count):
    # 除去数が多いパターンは破棄する
    if min_count[0] != -1 and count >= min_count[0]:
        return
    if index + 1 == len(array):
        # print("count:{}".format(count))
        min_count[0] = count if min_count[0] == - \
            1 or count < min_count[0] else min_count[0]
        return
    current = array[index]

    # 前のと手がぶつかる場合は取り除く
    if last_position >= current[2]:
        test(array, index + 1, last_position, count + 1, min_count)
    # 前のとぶつからない場合は取り除かないパターンも
    else:
        test(array, index + 1, index, count, min_count)


N = int(input())
array = [list(map(int, input().split())) for i in range(N)]
for line in array:
    line.append(line[0] - line[1])
    line.append(line[0] + line[1])
array = sorted(array, key=lambda x: x[3])

count = 0
max_r = -float('inf')
for i in range(N):
    current = array[i]
    # print(max_r)
    # print(current[2])
    if current[2] >= max_r:
        # print("残す")
        count += 1
        max_r = current[3]
# test(array, 0, -1, 0, min_count)
print(count)
n,m,d=map(int,input().split())

#全パターンの平均を求める＝期待値を求めれば良い
#ある隣り合う数(a,b)の組について、全パターンはn^2

#d=0の時、隣り合う数の組は(a,a)でなければならない
if d=0:
  C=n

#d≠0の時、隣り合う組のパターンは(1,1+d),(2,2+d)...(n-d,n)のn-d通り
#逆に(d+1,1)....の時も成り立つ
if d!=0:
  C=2*(n-d)
  
#上の組のパターンがm-1個の組について成り立つ
print((m-1)*C//n**2)

### FIXED CODE ###

n,m,d=map(int,input().split())
 
#全パターンの平均を求める＝期待値を求めれば良い
#ある隣り合う数(a,b)の組について、全パターンはn^2
 
#d=0の時、隣り合う数の組は(a,a)でなければならない
if d==0:
  C=n
 
#d≠0の時、隣り合う組のパターンは(1,1+d),(2,2+d)...(n-d,n)のn-d通り
#逆に(d+1,1)....の時も成り立つ
if d!=0:
  C=2*(n-d)
  
#上の組のパターンがm-1個の組について成り立つ
print((m-1)*C/(n**2))
n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
  ifa[i] >= m:
     cnt += 1
print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
  if a[i] >= m:
     cnt += 1
print(cnt)
import math

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

ans = 0

if c % d == 0:
    print((b - a + 1) - ((b)//d - (a-1)//d))
elif d % c == 0:
    print((b - a + 1) - ((b)//c - (a-1)//c))
else:
    tot = c * d // math.gcd(c, d)
    tmp = ((b) // d - (a-1) // d) + ((b)//c - (a-1)//c) - ((b) // tot - (a-1) // tot)
    print(int((b - a + 1) - tmp))

### FIXED CODE ###

import fractions

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

ans = 0

if c % d == 0:
    print((b - a + 1) - ((b)//d - (a-1)//d))
elif d % c == 0:
    print((b - a + 1) - ((b)//c - (a-1)//c))
else:
    tot = c * d // fractions.gcd(c, d)
    tmp = ((b) // d - (a-1) // d) + ((b)//c - (a-1)//c) - ((b) // tot - (a-1) // tot)
    print(int((b - a + 1) - tmp))
n = int(raw_input())
A = map(int,raw_input().split())
q = int(raw_input())
m = map(int,raw_input().split())

def solve(i,m):
     if m == 0:
        return 1
     if i >= n or m - sum(A) > 0:
        return 0
     res = solve(i+1,m) or solve(i+1,m-A[i])
        return res
  
for j in range(q):
     if solve(0,m[j]):
        print "yes"
     else:
        print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int,raw_input().split())
q = int(raw_input())
m = map(int,raw_input().split())

def solve(i,m):
  if m == 0:
    return 1
  if i >= n or m - sum(A) > 0:
    return 0
  res = solve(i+1,m) or solve(i+1,m-A[i])
  return res

for j in range(q):
  if solve(0,m[j]):
    print "yes"
  else:
    print "no"
N, T = map(int, input().split())
t = [int(i) for i in input().split()]
ans = T
wait = 0
start = 0
for i in range(1, N):
    if (t[i] - t[i - 1] >= T):
        ans += wait + T
        start = t[i]
        wait = 0
    else:
      wait = t[i] - start
        if (wait > T):
            ans, wait = ans + T, wait - T
print(ans + wait)


### FIXED CODE ###

N, T = map(int, input().split())
t = [int(i) for i in input().split()]
ans = T
for i in range(0, N-1):
  ans += min(t[i+1]-t[i],T)
print(ans)