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

import math
a,b,c,d,e,f = map(int,input().split())
max_sugar = f*e*100/(100+e)
box = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    if water > f:
      break
    for k in range(math.ceil(max_sugar/c)):
      for l in range(math.ceil(max_sugar/d)):
        sugar = c*k + d*l
        if sugar > max_sugar:
          break
        amount = water + sugar
        if amount == 0:
          break
        conc = 100*sugar / amount
        if amount <= f and conc <= e*100/(100+e):
          box[conc] = [amount,sugar]
answer = max(box.items(),key = lambda x:x[0])[1]
print(str(answer[0]) + " " +str(answer[1]))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
### BUGGY CODE ###

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

for A in range(1,N+1):
  print(X.count(A))

### FIXED CODE ###

import collections

N=int(input())
X=list(map(int, input().split()))
c = collections.Counter(X)

for A in range(1,N+1):
  print(c[A])
### BUGGY CODE ###

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

table = [1,1]
while len(table) <= N:
    temp = table[0]
    for i in range(len(table)-1):
        table[i+1] += temp
        temp = table[i+1]- temp
        table[i+1] %= M
    table.append(1)


S = [1]

rev2 = pow(2, M-2, M)
base = pow(2, N, M)
ans = 0
S = [1]
for K in range(N+1):
    res = table[K] % M
    res = (res * pow(2, pow(2, N - K, M-1), M)) % M
    b = 1
    v = 0
    T = [0]*(K+2)
    for L in range(K):
        T[L+1] = s = (S[L] + (L+1)*S[L+1]) % M
        v += s * b
        b = (b * base) % M
    v += b
    T[K+1] = 1
    S = T
    res = (res * v) % M
    if K % 2:
        ans -= res
    else:
        ans += res
    ans %= M

    base = (base * rev2) % M
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
fact = [1]*(N+1)
rfact = [1]*(N+1)
for i in range(1, N+1):
    fact[i] = r = (i * fact[i-1]) % M
    rfact[i] = pow(r, M-2, M)

S = [1]

rev2 = pow(2, M-2, M)
base = pow(2, N, M)
ans = 0
S = [1]
for K in range(N+1):
    res = (fact[N] * rfact[K] * rfact[N-K]) % M
    res = (res * pow(2, pow(2, N - K, M-1), M)) % M
    b = 1
    v = 0
    T = [0]*(K+2)
    for L in range(K):
        T[L+1] = s = (S[L] + (L+1)*S[L+1]) % M
        v += s * b
        b = (b * base) % M
    v += b
    T[K+1] = 1
    S = T
    res = (res * v) % M
    if K % 2:
        ans -= res
    else:
        ans += res
    ans %= M

    base = (base * rev2) % M
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ok = [0]*(max(a)+1)
a.sort()

for i in range(n):
    ok[a[i]] += 1
    if ok[a[i]] == 1:
        for g in range(2*a[i], max(a)+1, a[i]):
            ok[g] += 2


print(ok.count(1))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
M = max(a)
ok = [0]*(M+1)
a.sort()

for i in range(n):
    ok[a[i]] += 1
    if ok[a[i]] == 1:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] += 2


print(ok.count(1))
### BUGGY CODE ###

N = int(input())

l = []
for _ in range(N):
  a = int(input())
  if a in l:
    l.pop(l.index(a))
  else:
    l.append(a)

print(len(l))

### FIXED CODE ###

from collections import defaultdict

N = int(input())

dic = defaultdict(bool)
for _ in range(N):
  a = int(input())
  dic[a] = not dic[a]

print(sum(dic.values()))
### BUGGY CODE ###

import sys
import heapq

def main():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))

    h=[]
    for i in range(n):
        if b[i]>a[i]:
            heapq.heappush(h,[b[i]*-1,i])

    loop=0
    idx=0
    while(1):
    #print(b)
        if not h:
            break
        buf,idx=heapq.heappop(h)
        buf=-1*buf

        x=(buf-a[idx])//(b[(idx-1)%n]+b[(idx+1)%n])
        y=(buf-a[idx])%(b[(idx-1)%n]+b[(idx+1)%n])
        buf=a[idx]+y
        loop+=x
        b[idx]=buf
        if x==0:
            #print(b)
            print(-1)
            sys.exit()
        elif buf>a[idx]:
            heapq.heappush(h,[buf*-1,idx])

    print(loop)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq

def main():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))

    h=[]
    for i in range(n):
        if b[i]>a[i]:
            heapq.heappush(h,(b[i]*-1,i))

    loop=0
    idx=0
    while(1):
    #print(b)
        if not h:
            break
        buf,idx=heapq.heappop(h)
        buf=-1*buf

        x=(buf-a[idx])//(b[(idx-1)%n]+b[(idx+1)%n])
        buf-=x*(b[(idx-1)%n]+b[(idx+1)%n])
        loop+=x
        b[idx]=buf
        if x==0:
            #print(b)
            print(-1)
            sys.exit()
        elif buf>a[idx]:
            heapq.heappush(h,(buf*-1,idx))

    print(loop)

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

n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)
### BUGGY CODE ###

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

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

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):
    dp[i] = min(dp[max(0,i-K):i]+abs(h[max(0,i-K):i]-h[i]))

print(dp[-1])
### BUGGY CODE ###

def solve(_list,_k):
  start = 0
  _sum = -1
  for i in range(len(_list)-_k+1):
    s = sum(_list[i:i+_k])
    if _sum < s:
      _sum = s
      start = i

  ans = (_sum+_k) / 2
  return ans


if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)


### FIXED CODE ###

def solve(_list,_k):
  accumulate_list = [0.]
  for i in _list:
    accumulate_list.append((i+1)/2 + accumulate_list[-1])

  ans = -1.0
  for i in range(len(accumulate_list)-_k):
    ans = max(ans, accumulate_list[i+_k]-accumulate_list[i])
  return ans

if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
mod = 10**9 +7

dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
reach = [[False]*w for _ in range(h)]
que = deque(())

que.append((0,0))

while que:
    i,j = que.popleft()
    if i < h-1 and a[i+1][j] == '.':
        if dp[i+1][j] == 0:
            que.append((i+1,j))
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
    if j < w-1 and a[i][j+1] == '.':
        if dp[i][j+1] == 0:
            que.append((i,j+1))
        dp[i][j+1] += dp[i][j]
        dp[i][j+1] %= mod
print(dp[h-1][w-1])


### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
mod = 10**9 +7

dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
reach = [[False]*w for _ in range(h)]
que = deque(())

que.append((0,0))

while que:
    i,j = que.popleft()
    if i < h-1 and a[i+1][j] == '.':
        if dp[i+1][j] == 0:
            que.append((i+1,j))
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
    if j < w-1 and a[i][j+1] == '.':
        if dp[i][j+1] == 0:
            que.append((i,j+1))
        dp[i][j+1] += dp[i][j]
        dp[i][j+1] %= mod
print(dp[h-1][w-1])
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    if count > k:
        result = False
    else:
        result = True

    return result, count, mP

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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = 1000000000000
rangeMin = max(w)

while _:
    rangeMid = (rangeMax + rangeMin)//2

    if p(k,w,rangeMid)[0] == False and p(k,w,rangeMid+1)[0] == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid)[0] == True and p(k,w,rangeMid+1)[0] == True:
        rangeMax = rangeMid
    else:
        break

print(p(k,w,rangeMid+1)[2])

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

N, M = map(int, input().split())
P = []
Y = []
D = [[] for i in range(N)]
for i in range(M):
  p, y = map(int, input().split())
  P.append(p)
  Y.append(y)
  D[p-1].append(y)

ans = [None] * M
for i in range(len(D)):
  new_d = sorted(D[i])
  for j in range(len(new_d)):
    a = str(i+1).zfill(6)
    b = str(new_d.index(D[i][j])+1).zfill(6)
    n = Y.index(D[i][j])
    ans[n] = a+b
print(*ans, sep = '\n')

### FIXED CODE ###

N, M = map(int, input().split())
D = [[] for i in range(N)]

for i in range(M):
  p, y = map(int, input().split())
  D[p-1].append((y, i)) #市ごとにリストに入れる．この時，元の順番をタプルの1番目の要素として入れておく

ans = [None]*M

for i, d in enumerate(D): #enumerateは要素の中身とインデックス番号を持ってこれる．print(i, d)で確認
  d.sort()
  for k, (y, j) in enumerate(d): #こちらも同様．(y, j)となっているため，yには年数が，jには元の順番の情報が入る
    ans[j] = str(i+1).zfill(6) + str(k+1).zfill(6) #ans[j]に12桁の認識番号を挿入

print(*ans, sep = '\n')
### BUGGY CODE ###

n, m = map(int, input().split())
lst = [0 for i in range(n+1)]
cnt = 0
for _ in range(m):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        lst[i] += 1 

cnt = lst.count(m)
print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
l_list = []
r_list = []
cnt = 0
for _ in range(m):
    l, r = map(int, input().split())
    l_list.append(l)
    r_list.append(r)

print(min(r_list) - max(l_list) + 1) if min(r_list) >= max(l_list) else print(0)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

for i in range(int(N)):
	print(a.count(i+1))

### FIXED CODE ###

N = input()
N = int(N)
a = list(map(int,input().split()))
s =[0]*N
for i in range(N-1):
	s[a[i]-1]+=1
    
for i in range(N):
	print(s[i])
### BUGGY CODE ###

import math
N = int(input())
for n in range(1, N+1):
  counter = 0
  if n < 6:
    print(0)
    continue
  x = y = z = 0
  x_max = math.ceil(1/3*(2 * math.sqrt(3*n-2)-1))
  while x <= x_max:
    y = 1
    while x >= y:
      y += 1
    x += 1
    while 4*n-3*x**2-2*x*y-3*y**2 >= 0:
      s = math.sqrt(4*n-3*x**2-2*x*y-3*y**2)
      if float(s).is_integer():
        s = int(s)
        if (s-x-y) >= 2 and (s-x-y) % 2 == 0 and x == y == int((s-x-y)/2):
          counter += 1
        elif (s-x-y) >= 2 and (s-x-y) % 2 == 0 and x <= y <= (s-x-y)/2:
          z = int((s-x-y)/2)
          #print("n:" + str(n) + "(" + str(x) + "," + str(y) + "," + str(z) + ")")
          counter += 3
      y += 1
  print(counter)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = i*i+j*j+k*k+i*j+j*k+k*i;
      if v<10050:
        ans[v]+=1
for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
y = 0
for i in range(2 ** n):
  v_total = 0
  c_total = 0
  for j in range(n):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      v_total += v[j]
      c_total += c[j]
  if (v_total-c_total) > y:
    y = v_total-c_total
print(y)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
y = 0
for i in range(2 ** n):
  v_total = 0
  c_total = 0
  for j in range(n):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      v_total += v[j]
      c_total += c[j]
  if (v_total-c_total) > y:
    y = v_total-c_total
print(y)
### BUGGY CODE ###

def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    input = sys.stdin.readline

    MAX  = 10 ** 15

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

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = dijkstra(g1, directed = False, indices = s - 1)
    d2 = dijkstra(g2, directed = False, indices = t - 1)

    d = d1 + d2

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d[i])
        ans[i] -= int(tmp)

    print (*ans, sep = '\n')

if __name__ == "__main__":
    main()



### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

MAX  = 10 ** 15

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

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d1[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g1[v])): #頂点vの隣接リストを走査
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: #距離が更新できるかを検討
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d1)

d2[t] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, t]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d2[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g2[v])): #頂点vの隣接リストを走査
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: #距離が更新できるかを検討
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d2)

tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

print (*ans, sep = '\n')
### BUGGY CODE ###

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

flag = True
for i in range(N):
  for j in range(i+1, N):
    if A[i] == A[j]:
      flag = False
      break
if flag:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

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

flag = True
A = sorted(A)
for i in range(N-1):
  if A[i] == A[i+1]:
    flag = False
if flag:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N,K = map(int, input().split())
p = list(map(int, input().split()))
for i in range(N):
    p[i] = 0.5*(p[i]+1)

ans,i = 0,0
while i+K <= N:
    psum = sum(p[i:i+K])
    if psum > ans:
        ans = psum
    i += 1

print(ans)

### FIXED CODE ###

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

st = 0
i = 0
sa = 0
while i+K < N:
    sa += p[i+K]-p[i]
    if sa > 0:
        st = i+1
        sa = 0
    i += 1

psum = p[st:st+K]
for i in range(K):
    psum[i] = (psum[i]+1)/2
print(sum(psum))
### BUGGY CODE ###

s = str(input())
n = len(s)

cum = [[0]*(n+1) for _ in range(26)]

for i in range(26):
    c = chr(i + ord('a'))
    for j in range(n):
        if s[j] == c:
            cum[i][j+1] = cum[i][j]+1
        else:
            cum[i][j+1] = cum[i][j]


for i in range(26):
    for j in range(n+1):
        cum[i][j] = 2*cum[i][j] -j

from collections import deque

for i in range(26):
    min_ = 10**6
    min_id = -1
    q = deque()
    for j in range(n+1):
        if j == 0:
            q.append((cum[i][j], j))
        elif j == 1:
            q.append((cum[i][j], j))
        else:
            temp, temp_id = q.popleft()
            if temp <= min_:
                min_ = temp
                min_id = temp_id
            if cum[i][j] - min_ > 0:
                print(min_id+1, j)
                exit()
            q.append((cum[i][j], j))
else:
    print(-1, -1)

### FIXED CODE ###

s = str(input())
n = len(s)

cum = [[0]*(n+1) for _ in range(26)]

for i in range(26):
    c = chr(i + ord('a'))
    for j in range(n):
        if s[j] == c:
            cum[i][j+1] = cum[i][j]+1
        else:
            cum[i][j+1] = cum[i][j]


for i in range(26):
    for j in range(n+1):
        cum[i][j] = 2*cum[i][j] -j

from collections import deque

for i in range(26):
    min_ = 10**6
    min_id = -1
    q = deque()
    for j in range(n+1):
        if j == 0:
            q.append((cum[i][j], j))
        elif j == 1:
            q.append((cum[i][j], j))
        else:
            temp, temp_id = q.popleft()
            if temp <= min_:
                min_ = temp
                min_id = temp_id
            if cum[i][j] - min_ > 0:
                print(min_id+1, j)
                exit()
            q.append((cum[i][j], j))
else:
    print(-1, -1)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        x, l = map(int, input().split())
        XL.append((x, l))
    XL.sort(key=lambda p: p[0] - p[1])

    inf = 10**10
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = -inf
    for i in range(N):
        x, l = XL[i]
        for j in range(N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j < N:
                if dp[i][j] <= x - l:
                    dp[i+1][j+1] = min(dp[i+1][j+1], x + l)
    for i in range(N, -1, -1):
        if dp[-1][i] < 10**10:
            print(i)
            exit()


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        x, l = map(int, input().split())
        XL.append((x, l))
    XL.sort(key=lambda p: p[1] + p[0])

    ans = 0
    prev = -10**10
    for i in range(N):
        x, l = XL[i]
        if x - l >= prev:
            ans += 1
            prev = x + l
    print(ans)


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

n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = float('inf')
for i in range(n-k+1):
  g = min(g, max(h[i:i+k]) - min(h[i:i+k]))
print(g)

### FIXED CODE ###

n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = float('inf')
for i in range(n-k+1):
  g = min(g, h[i+k-1] - h[i])
print(g)
### BUGGY CODE ###


x=int(input())
value=0
index=0
hashmap=dict()
while value<int(1e9)+1:
    value=pow(index,5)
    hashmap[value]=index
    index+=1
#print(hashmap)    

for i in range(1,x+1):
    b1=x+int(pow(i,5))
    b2=x+int(pow(-i,5))
#    print(i,b1,b2)
    if hashmap.get(b1)!=None:
        print(hashmap[b1],i)
        break
    if hashmap.get(b2)!=None:
        print(hashmap[b2],-i)
        break     

### FIXED CODE ###

x=int(input())
value=0
index=0
hashmap=dict()
while value<int(1e18)+1:
    value=pow(index,5)
    hashmap[value]=index
    index+=1

for i in range(1,1000):
    b1=x+int(pow(i,5))
    b2=x+int(pow(-i,5))
#    print(i,b1,b2)
    if hashmap.get(b1)!=None:
        print(hashmap[b1],i)
        break
    if hashmap.get(b2)!=None:
        print(hashmap[b2],-i)
        break