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

N, M = map(int, input().split())
K = []

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(int, input().split()):
        k |= (1 << (i - 1))
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        dp[state | k] = min(dp[state | k], dp[state] + a)

ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M = map(int, input().split())
    keys = []

    for _ in range(M):
        a, _ = map(int ,input().split())
        C = list(map(int, input().split()))
        cMask = 0
        for c in C:
            cMask |= (1 << (c - 1))
        keys.append((a, cMask))

    dp = [[INF] * (1 << N) for _ in range(M + 1)]  # dp[i][mask] = i番目の鍵までで，状態mask
    dp[0][0] = 0

    for i, (cost, cMask) in enumerate(keys, start=1):
        for mask in range(1 << N):
            dp[i][mask] = min(dp[i][mask], dp[i - 1][mask])
            dp[i][mask | cMask] = min(dp[i][mask | cMask], dp[i - 1][mask] + cost)

    ans = dp[M][(1 << N) - 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)

sol()
### BUGGY CODE ###

a, b = map(int, input().split())
cnt = 0
for i in range(a+1):
    if i > b: break
    for j in range(a+1):
        if i + j > b: break
        for k in range(a+1):
            if i + j + k > b: break
            if i + j + k == b:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from statistics import mean

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

S = [A[0]]
for i in range(1, N):
    S.append(S[i - 1] + A[i])   


ans = float('inf')

for middle in range(1, N - 2):
    left_middle = 0
    right_middle = middle + 1
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

print(ans)
        


### FIXED CODE ###

from statistics import mean

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

S = [A[0]]
for i in range(1, N):
    S.append(S[i - 1] + A[i])   

left_middle = 0
right_middle = 2

ans = float('inf')

for middle in range(1, N - 2):
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

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

from operator import mul
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

out = reduce(mul, A)

if out <= 1e18:
  print(out)
else:
  print('-1')

### FIXED CODE ###

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

A.sort(reverse=True)
out = 1
if A[-1] == 0:
  out = 0
else:
  for i in A:
    out *= i
    if out > 1e18:
      out = -1
      break
print(out)
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while len(que) != 0:
    from_v, to_v = que.pop()
    dist[to_v] = dist[from_v] + 1
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.appendleft((to_v,next_v))
if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)


### FIXED CODE ###

from sys import stdin
from collections import defaultdict
from collections import deque

N,M = list(map(int,stdin.readline().split()))
Cs = [tuple(map(int,stdin.readline().split())) for _ in range(M)]
S,T = list(map(int,stdin.readline().split()))

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
dist[S] = 0
que.append(S)
while len(que) != 0:
    from_v = que.popleft()
    nexts = graph_connection[from_v]
    for next_v in nexts:
        if dist[next_v] == -1:
            dist[next_v] = dist[from_v] + 1
            que.append(next_v)

if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)
### BUGGY CODE ###

x = int(input())
def check(i):
    a = 1
    while True:
        b = a - i
        temp = pow(a, 5) - pow(b, 5)
        #if i == 17:print(temp, a, b)
        if temp == x:
            return (a, b)
        if b > 0 and temp > x:
            return -1
        a += 1

num = int(pow(x, 0.5)//1)
for i in range(1, num + 1):

    if x % i == 0:
        temp = check(i)
        temp1 = check(x//i)
        if temp == -1 and temp1 == -1:continue
        else:
            if temp != -1:print(*temp)
            else:print(*temp1)
            exit()

### FIXED CODE ###

x = int(input())
def check(i):
    a = 1
    while True:
        b = a - i
        temp = pow(a, 5) - pow(b, 5)
        #if i == 17:print(temp, a, b)
        if temp == x:
            return (a, b)
        if b > 0 and temp > x:
            return -1
        a += 1

num = int(pow(x, 0.5)//1)
for i in range(1, num + 1):

    if x % i == 0:
        temp = check(i)
        if temp == -1:continue
        else:
            print(*temp)
            exit()
### BUGGY CODE ###

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

A, B, C, K = mapint()
for _ in range(K):
    A, B, C = B+C, A+C, A+B
    if abs(A-B)>10**18:
        print('Unfair')
        break
    if A-B==0:
        print(0)
        break
else:
    print(A-B)

### FIXED CODE ###

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

A, B, C, K = mapint()
if K%2==0:
    print(A-B)
else:
    print(B-A)
### BUGGY CODE ###

h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]
  for j in range(f):
    if j+a[i-1]<f:
      dp[i][j+a[i-1]]=min(dp[i][j+a[i-1]],dp[i][j]+b[i-1])
  for j in range(f-1,0,-1):
    dp[i][j-1]=min(dp[i][j-1],dp[i][j])
print(dp[-1][h])


### FIXED CODE ###

h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
#dp[i][j]=i番目までの魔法を使えるとき、体力をj減らす最小魔力
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f):
    dp[i][j]=dp[i-1][j]
    if j-a[i-1]>=0:dp[i][j]=min(dp[i][j],dp[i][j-a[i-1]]+b[i-1])
print(min(dp[-1][h:]))
### BUGGY CODE ###

import sys
import copy

N = int(input())
b = [int(b) for b in input().split()]
a = []

def f(b):
  if len(b) == 1:
    return(b if b[0] == 1 else [])
  for i in range(len(b)):
    if b[i] == i + 1:
      b_sub = copy.copy(b)
      b_i = b_sub.pop(i)
      a = f(b_sub)
      if len(a) != 0:
        a.append(b_i)
        return(a)
  return([])

a = f(b)
if len(a) == 0:
  print(-1)
else:
  for i in range(N):
    print(a[i])

### FIXED CODE ###

import sys
import time
import copy

N = int(input())
b = [int(b) for b in input().split()]
h = {}

t1 = time.time()

def f(b):
  t2 = time.time()
  if t2 - t1 > 1.5:
    print(-1)
    sys.exit()
  
  key = "".join([str(x) for x in b])
  if key in h:
    return copy.copy(h[key])
  
  if len(b) == 1:
    h[key] = b if b[0] == 1 else []
    return copy.copy(h[key])
  
  for i in range(len(b)):
    i = len(b) - 1 - i
    if b[i] == i + 1:
      b_sub = copy.copy(b)
      b_i = b_sub.pop(i)
      a = f(b_sub)
      if len(a) != 0:
        a.append(b_i)
        h[key] = a
        return copy.copy(h[key])
  
  h[key] = []
  return copy.copy(h[key])

a = f(b)
if len(a) == 0:
  print(-1)
else:
  for i in range(N):
    print(a[i])
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
dic = [''.join(sorted(i)) for i in s]
key = [i for i in set(dic)]
cnt = 0
for i in key:
    a = dic.count(i)-1
    cnt += (a * (a+1))/2
print(int(cnt))


### FIXED CODE ###

n = int(input())
s = {}
cnt = 0
for i in range(n):
    j = ''.join(sorted(input()))
    if j in s:
        s[j] += 1
    else:
        s[j] = 0
    cnt += s[j]
print(int(cnt))
### BUGGY CODE ###

num = int(input())
value = [input() for i in range(num)]
string_count = list(set(value))
string_count.sort()
number = 0
list_data = list()
for data in string_count:
    if number == value.count(data):
        list_data.append(data)
    elif number < value.count(data):
        number = value.count((data))
        list_data = []
        list_data.append(data)

for i in list_data:
    print(i)

### FIXED CODE ###

from collections import Counter
num = int(input())
value = [input() for i in range(num)]
votes = Counter(value)
dict = {}

for value in votes.values():
    dict[value] = []

for (key, value) in votes.items():
    dict[value].append(key)
maxVote = sorted(dict.keys(), reverse=True)[0]
list_data = dict[maxVote]
list_data.sort()
for i in list_data:
    print(i)
### BUGGY CODE ###

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

S = input()
items = []
for i in range(Q):
    items.append(input().split())

left_ok = -1
left_ng = N

while abs(left_ng - left_ok) > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while abs(right_ok - right_ng) > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    tmp = mid
    for t, d in items:
        if t == S[tmp]:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
        
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

print(ans)


### FIXED CODE ###

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

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

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

N,M=map(int,input().split())
while True:
    b = abs(N-M)
    if b<N:
        N=b
    else:
        break
print(N)

### FIXED CODE ###

N,K=map(int,input().split())
a = N%K
if abs(a-K)<a:
    print(abs(a-K))
else:
    print(a)
### BUGGY CODE ###

from itertools import permutations, product

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

for k, i, j in product(range(N), repeat=3):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += dist[s][g]
    ans = min(ans, d)
print(ans)

### FIXED CODE ###

from itertools import permutations, product

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

for k, i, j in product(range(N), repeat=3):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += dist[s][g]
    ans = min(ans, d)
print(ans)
### BUGGY CODE ###

from math import factorial

n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
s=0

#maxについて
for i in range(k-1,n):
	s+=a[i]*factorial(i)//factorial(k-1)//factorial(i-k+1)
	s%=10**9+7
for i in range(n-k+1):
	s-=a[i]*factorial(n-i-1)//factorial(k-1)//factorial(n-k-i)
	s%=10**9+7
print(s)

### FIXED CODE ###

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
MOD=10**9+7

fac, ifac=make_tables(MOD,n)

s=0
for i in range(k-1,n):
	s+=(a[i]-a[n-i-1])*cmb(i,k-1,MOD,fac,ifac)
	s%=10**9+7
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([''] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = dp[i][j + 1]
            if len(dp[i + 1][j + 1]) < len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            if len(dp[i + 1][j + 1]) < (len(dp[i][j]) + int(x == y)):
                dp[i + 1][j + 1] = dp[i][j] + x
    return dp[-1][-1]


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([0] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(x == y))

    s = []
    p = (-1, -1)
    while 0 < dp[p[0]][p[1]]:
        if dp[p[0]][p[1]] == dp[p[0]-1][p[1]]:
            p = (p[0]-1, p[1])
        elif dp[p[0]][p[1]] == (dp[p[0]-1][p[1]-1] + int(xs[p[0]] == ys[p[1]])):
            s.append(xs[p[0]])
            p = (p[0]-1, p[1]-1)
        else:
            p = (p[0], p[1]-1)

    return ''.join(reversed(s))


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    print(result)

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

def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



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

n, x, y = map(int, input().split())
x = min(x - 1, y - 1)
y = max(x - 1, y - 1)
length = [0] * (n - 1)
for i in range(n - 1):
    for j in range(i, n):
        l = min(abs(i - j), abs(i - x) + 1 + abs(j - y), abs(i - y) + 1 + abs(j - x))
        if l != 0:
            length[l - 1] += 1
for l in length:
    print(l)

### FIXED CODE ###

n, x, y = map(int, input().split())
x = min(x - 1, y - 1)
y = max(x - 1, y - 1)
length = [0] * (n - 1)
for i in range(n - 1):
    for j in range(i, n):
        l = min(abs(i - j), abs(i - x) + 1 + abs(j - y), abs(i - y) + 1 + abs(j - x))
        if l != 0:
            length[l - 1] += 1
for l in length:
    print(l)
### BUGGY CODE ###

n = int(input())

machines = []
for i in range(n):
  x, l = map(int, input().split())
  machines.append([x+l, x-l])
machines.sort()

stock = []
stock.append(machines.pop(0))
while len(machines) > 0:
  point = machines.pop(0)
  if stock[-1][0] > point[1]:
    continue
  else:
    stock.append(point)

print(len(stock))

### FIXED CODE ###

n = int(input())

machines = []
for i in range(n):
  x, l = map(int, input().split())
  machines.append([x+l, x-l])
machines.sort()

ans = 1
first = machines.pop(0)
stock_r = first[0]
for r,l in machines:
  if stock_r > l:
    continue
  else:
    ans += 1
    stock_r = r

print(ans)