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

# これ愚直じゃダメなのかな
# 上下左右それぞれのテーブルを用意し、いまいるところより上/下/左/右にいくつあるかをセーブする（自分は含まない）
# ↑ この4方向累積和方針はあってるっぽいけど愚直に4方向のテーブルを作ってみたいな方針でやったらTLEなった。あとは頼む
# ↑ やりました（4ヶ月ぶり）
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))

toR, toL = (
    [[0 for _ in range(w + 1)] for _ in range(h)],
    [[0 for _ in range(w + 1)] for _ in range(h)],
)
toU, toD = (
    [[0 for _ in range(w)] for _ in range(h + 1)],
    [[0 for _ in range(w)] for _ in range(h + 1)],
)


for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            toR[y][x + 1] += toR[y][x] + 1
            toD[y + 1][x] += toD[y][x] + 1
        else:
            toR[y][x + 1] = 0
            toD[y + 1][x] = 0

        if grid[y][w - x - 1] == ".":
            toL[y][w - x - 1] += toL[y][w - x] + 1
        else:
            toL[y][w - x - 1] = 0

        if grid[h - y - 1][x] == ".":
            toU[h - y - 1][x] += toU[h - y][x] + 1
        else:
            toU[h - y - 1][x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        tmp = toR[y][x + 1] + toL[y][x] + toD[y + 1][x] + toU[y][x] - 3
        ans = max(ans, tmp)

print(ans)



### FIXED CODE ###

# これ愚直じゃダメなのかな
# 上下左右それぞれのテーブルを用意し、いまいるところより上/下/左/右にいくつあるかをセーブする（自分は含まない）
# ↑ この4方向累積和方針はあってるっぽいけど愚直に4方向のテーブルを作ってみたいな方針でやったらTLEなった。あとは頼む
# ↑ やりました（4ヶ月ぶり） -> 駄目でした TLE
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))

toR, toL = (
    [[0 for _ in range(w + 1)] for _ in range(h)],
    [[0 for _ in range(w + 1)] for _ in range(h)],
)
toU, toD = (
    [[0 for _ in range(w)] for _ in range(h + 1)],
    [[0 for _ in range(w)] for _ in range(h + 1)],
)


for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            toR[y][x + 1] += toR[y][x] + 1
            toD[y + 1][x] += toD[y][x] + 1
        else:
            toR[y][x + 1] = 0
            toD[y + 1][x] = 0

        if grid[y][w - x - 1] == ".":
            toL[y][w - x - 1] += toL[y][w - x] + 1
        else:
            toL[y][w - x - 1] = 0

        if grid[h - y - 1][x] == ".":
            toU[h - y - 1][x] += toU[h - y][x] + 1
        else:
            toU[h - y - 1][x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        tmp = toR[y][x + 1] + toL[y][x] + toD[y + 1][x] + toU[y][x] - 3
        ans = max(ans, tmp)

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

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for i, ti in enumerate(t):
        u, v = v, v.copy()
        dp.append(v)
        for j, sj in enumerate(s):
            if sj == ti:
                v[j + 1] = 1 + u[j]
            else:
                v[j + 1] = u[j + 1]
                tmp = v[j]
                if v[j + 1] < tmp:
                    v[j + 1] = tmp
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())
### BUGGY CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[{0}for _ in range(w)]
dp[0]={a[0][0]-b[0][0],b[0][0]-a[0][0]}
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    t=set()
    if i:
      t|=set(t+x-y for t in dp[j])
      t|=set(t-x+y for t in dp[j])
    if j:
      t|=set(t+x-y for t in dp[j-1])
      t|=set(t-x+y for t in dp[j-1])
    if i+j:dp[j]=t
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))
### BUGGY CODE ###

def median(list):
    list.sort()
    median = list[int((len(list)+1)/2)-1]
    return median

if __name__ == "__main__":

    n = int(input())

    number_list = list(map(int,input().split()))

    for i in range(n):
        m = median(number_list[:i]+number_list[i+1:])
        print(m)


### FIXED CODE ###



n = int(input())

number_list = list(map(int,input().split()))
tmp_list = sorted(number_list)


for number in number_list:
    if number < tmp_list[n//2]:
        print(tmp_list[n//2])
    else :
        print(tmp_list[n//2-1])
### BUGGY CODE ###

import sys
n,k = map(int,input().split())
h = list(map(int,sys.stdin.readline().split()))

dp = [0] * n
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))

print(dp[-1])


### FIXED CODE ###

import sys
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,sys.stdin.readline().split())))

dp = np.zeros(n, dtype=int)
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    #dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))
    dp[i] = (dp[x:i] + abs(h[i] - h[x:i])).min()
print(dp[-1])
### BUGGY CODE ###

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

    mod_value = 10**9 + 7
    sum_ = 0
    for i in range(len(A)-1):
        sum_ = sum_ + A[i]*sum(A[i+1:]) % mod_value
    print(sum_ % mod_value)
main()

### FIXED CODE ###

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

    mod_value = 10**9 + 7
    sum_ = 0
    b_sum = 0
    for i in range(len(A)-1):
        b_sum = b_sum + A[len(A)-i-1]
        sum_ = sum_ + (A[len(A)- i - 2]*b_sum) % mod_value
    print(sum_%mod_value)
main()
### BUGGY CODE ###

from collections import deque

q = deque(input())
Q = int(input())
reverse = -1

for i in range(Q):
    X = input().split()
    if X[0] == "1":
        reverse *= -1
    # if X[1] == "1":
    elif X[1] == "1":
        if reverse == -1:
            q.appendleft(X[2])
        else:
            q.append(X[2])
    elif X[1] == "2":
        if reverse == -1:
            q.append(X[2])
        else:
            q.appendleft(X[2])
if reverse == 1: q.reverse()

for i in range(len(q)):
    print(q[i],end="")
print()


### FIXED CODE ###

from collections import deque

q = deque(input())
Q = int(input())
reverse = -1

for i in range(Q):
    X = input().split()
    if X[0] == "1":
        reverse *= -1
    # if X[1] == "1":
    elif X[1] == "1":
        if reverse == -1:
            q.appendleft(X[2])
        else:
            q.append(X[2])
    elif X[1] == "2":
        if reverse == -1:
            q.append(X[2])
        else:
            q.appendleft(X[2])
# if reverse == 1: q.reverse()

if reverse == -1:
    print(''.join(q))
else:
    print(''.join(list(q)[::-1]))
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = set()
        for j in g[i]:
            if di > d[j]:
                remove_list.add(j)
        g[i] -= remove_list
    dd = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])[::-1]]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())

d = (aa + bb for aa in a for bb in b)
d = sorted(d, reverse=True)[:K]

e = (cc + dd for cc in c for dd in d)
e = sorted(e, reverse=True)[:K]

print('\n'.join(map(str, e)))

### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

k = input()
s = raw_input()

left = 0; right = int(s)
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = 0
    for c in s:
        now = 10*now + int(c)
        if now > mid:
            cnt += 1
            now = int(c)
            if now > mid:
                cnt = 100003
                break
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1


### FIXED CODE ###

k = input()
s = raw_input()

if k==0:
    print s
    exit(0)
if len(s) % (k+1) == 0:
    p = len(s) / (k+1)
    print max(int(s[i:i+p]) for i in xrange(0,len(s),p))
    exit(0)

l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = 10**(l-1)
right = 10**r
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = ""
    mid_c = str(mid)
    cp = idx = 0
    for c in s:
        now += c
        if not cp and idx < len(mid_c) and c != mid_c[idx]:
            cp = 1 if c > mid_c[idx] else -1
        idx += 1
        if (idx == len(mid_c) and cp == 1) or idx > len(mid_c):
            cnt += 1
            idx = 1; cp = 0
            if int(c) > mid:
                cnt = 100003
                break
            now = c
            if c != mid_c[0]:
                cp = 1 if c > mid_c[0] else -1
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[10 ** 9 + 1] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=10 ** 9 + 1)
    d = floyd_warshall(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


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

import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
d = 1
while r > 0:
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()

print(d)


### FIXED CODE ###

import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
orgr = r
d = 1
for _ in range(K + 1):
    if r == 0:
        print(d)
        break
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()
    dict[r] = True
### BUGGY CODE ###

from itertools import accumulate
n = int(input())
a = [int(i) for i in input().split()]
b = list(accumulate(a))
ans = 0
c = list(set(b))
for cc in c:
    num = b.count(cc)
    if num > 1:
        ans += (num * (num - 1)) // 2
ans += b.count(0)
print(ans)

### FIXED CODE ###

from itertools import accumulate
import collections
n = int(input())
a = [int(i) for i in input().split()]
b = list(accumulate(a))
c = collections.Counter(b)
ans = sum([((num * (num - 1)) // 2) for num in c.values()])
ans += c[0]
print(ans)
### BUGGY CODE ###

N = int(input())
s_list = ["".join(sorted(input())) for _ in range(N)]
s_set = set(s_list)
ans = 0

for D in s_set:
  num = s_list.count(D) 
  ans += (num * (num-1)) // 2
  
print(ans)

### FIXED CODE ###

N = int(input())
count = {}
ans = 0

for _ in range(N):
    ele = "".join(sorted(input()))
    if ele in count.keys():
        ans += count[ele]
        count[ele] += 1
    else:
        count[ele] = 1
  
print(ans)
### BUGGY CODE ###

N=int(input())
Paper=[]
for i in range(N):
  A=int(input())
  if A in Paper:
    Paper.remove(A)
  else:
    Paper.append(A)
print(len(Paper))

### FIXED CODE ###

N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)
### BUGGY CODE ###

import sys

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    total_pass = 0
    for i, i_A in enumerate(A_list):
        for j in range(i+i_A, N):
            if (j - i) == i_A + A_list[j]:
                total_pass += 1

    print(total_pass)

    return

if __name__ == '__main__':
    main()
    sys.exit(0)

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    h_list = [0] * N

    for i, i_A in enumerate(A_list):
        if i - i_A >= 0:
            h_list[i-i_A] += 1

    total_pair = 0
    for i, i_A in enumerate(A_list):
        if i+i_A <= N-1:
            total_pair += h_list[i+i_A]

    print(total_pair)
    return
    
if __name__ == '__main__':
    main()
    sys.exit(0)
### BUGGY CODE ###

import sys
 
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
ans=[0]*n
memo = [False for i in range(n)]
dfs(0,0)
 
print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]
 
#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())


dat = []
for _ in range(n):
    x, l = map(int, input().split())
    #           0  1   2    3    4co     5
    dat.append([x, l, x-l, x+l, 0     , []])
dat.sort(key = lambda x: x[1], reverse=True)
#print(dat)
res = []
res_safe = []
def do_count():
    for i in range(n):
        #print("i={0}".format(i))
        c = 0
        m = []
        for j in range(i+1, n):
            #print("j={0}".format(j))
            if dat[j][3] <= dat[i][2] or dat[i][3] <= dat[j][2]:
                pass
            else:
                dat[i][5].append(dat[j])
                dat[j][5].append(dat[i])
                dat[i][4] += 1
                dat[j][4] += 1

do_count()
dat.sort(key = lambda x: (x[4], x[1]), reverse=True)
#print(dat)
for i in range(n):
    if dat[i][4] == 0:
        res.append(dat[i])
        continue
    #print("node {0}: kill".format(i))
    for node in dat[i][5]:
        #print(node[5])
        for x in range(len(node[5])):
            if node[5][x] == dat[i]:
                node[4] -= 1
                del node[5][x]
                #print("!!!!")

#print(res)
print(len(res))


### FIXED CODE ###

n = int(input())
dat = []
for _ in range(n):
    x, l =map(int, input().split())
    dat.append([x-l, x+l])
dat.sort(key=lambda x: x[1])
#print(dat)
prevr = -99999999999999999
res = 0
for i in range(n):
    if dat[i][0] >= prevr:
        prevr = dat[i][1]
        res += 1
print(res)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(N):
        step = i+2
        if i+1 in A:
            dp[step] = 0
        else:
            dp[step] = dp[step-1] + dp[step-2]
            dp[step] %= MOD

    return dp[N+1]


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+1)
    for a in A:
        is_safe[a] = False

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(N):
        step = i+2
        if is_safe[i+1]:
            dp[step] = dp[step-1] + dp[step-2]
            dp[step] %= MOD
        else:
            dp[step] = 0

    return dp[N+1]


if __name__ == '__main__':
    print(main())