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

def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

    ranges = []
    for i in range(N):
        ranges.append((X[i] - L[i], X[i] + L[i]))
    ranges.sort(key=lambda x: x[0])

    while True:
        dup = [0 for i in range(len(ranges))]
        for i in range(len(ranges) - 1):
            if ranges[i][1] > ranges[i + 1][0]:
                dup[i] += 1
                dup[i + 1] += 1

        remove_index = [(i, dup[i]) for i in range(len(dup))]
        remove_index.sort(key=lambda x: x[1], reverse=True)
        if remove_index[0][1] == 0:
            break
        ranges.pop(remove_index[0][0])
    print(len(ranges))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

    ranges = []
    for i in range(N):
        ranges.append((X[i] - L[i], X[i] + L[i]))
    ranges.sort(key=lambda x: x[1])

    cnt = len(ranges)
    end = ranges[0][1]
    for i in range(1, len(ranges)):
        if ranges[i][0] < end:
            cnt -= 1
        else:
            end = ranges[i][1]
    print(cnt)


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

import math
import sys

place_count = int(input())
position_list = input().split()

now_position = 0
cost = 0

for skip_position in position_list:
	skip_position = int(skip_position)
	for next_position in position_list:
		next_position = int(next_position)
		if skip_position == next_position:
			continue
		cost += abs(next_position - now_position)
		now_position = next_position
	cost += abs(now_position)
	print(cost)
	now_position = 0
	cost = 0


### FIXED CODE ###

place_count = int(input())
position_list = [0] + list(map(int, input().split()))
position_list.append(0)

all_sum = 0

for i in range(0, place_count+1):
	all_sum += abs(position_list[i+1] - position_list[i])

for x in range(1, place_count+1):
	print(all_sum - abs(position_list[x-1] - position_list[x]) - abs(position_list[x+1] - position_list[x]) + abs(position_list[x+1] - position_list[x-1]))
### BUGGY CODE ###

def find_dex(list,dex):
    for j in range(len(list)):
        if list[j][0] == dex:
            return j
    return 0
n = int(input())
d = []
left = []
right = []
for i in range(n):
    x,l = map(int, input().split())
    # num , left , right
    left.append([i,x-l+1,x+l-1])
    right.append([i,x-l+1,x+l-1])

left.sort(key=lambda x:x[1],reverse=False)
right.sort(key=lambda x:x[2],reverse=False)

flag = True
p = 10**9 + 1
ans = 0
while len(left) > 0:
    if flag:
        i,l,r = left.pop(-1)
        right.pop(find_dex(right,i))
        flag = False
        if r >= p:
            ans += 1
        p = l

    else:
        i,l,r = right.pop(-1)
        left.pop(find_dex(left,i))
        flag = True
        if r >= p:
            ans += 1
        p = l

    #print(i,l,r)
    #print(left)
    #print(right)

print(n-ans)


### FIXED CODE ###

n = int(input())
d = []
left = []
right = []
for i in range(n):
    x,l = map(int, input().split())
    # num , left , right
    d.append([x-l,x+l])

d.sort()
p = d[0][1]
ans = n
for i in range(1,n):
    if d[i][0] < p:
        ans -= 1
        p = min(p,d[i][1])
    else:
        p = d[i][1]
print(ans)
### BUGGY CODE ###

import numpy as np

N,H=list(map(int,input().split()))
a,b=np.transpose([list(map(int,input().split())) for _ in range(N)])

amax=max(a)
b=sorted(b,reverse=True)
res=10**10

for i in range(N+1):
    cnt=i
    ch=H

    ch-=sum(b[:i]) if i>0 else 0
    if H>0:
        cnt+=int(np.ceil(ch/amax))

    res=min(res,cnt)

print(res)    


### FIXED CODE ###

N,H=list(map(int,input().split()))
a=[0]*N
b=[0]*N

for i in range(N):
    ta,tb=list(map(int,input().split()))
    a[i]=ta
    b[i]=tb

amax=max(a)
b.sort(reverse=True)

res=10**10
csum=0
for i in range(N+1):
    cnt=i
    ch=H
    csum+=b[i-1] if i>0 else 0
    ch-=csum

    if ch>0:
        cnt+=-(-ch//amax)

    res=min(res,cnt)

print(res)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
rec = 1

for i in a:
    rec = rec * i
if rec > 10 ** 18:
    print(-1)
else:
    print(rec)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
rec = 1
if 0 in a:
    print(0)
    exit()

for i in a:
    rec = rec * i
    if rec > 10 ** 18:
        print(-1)
        exit()
print(rec)
### BUGGY CODE ###

import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

N, M = map(int, input().split())
G = nx.Graph()

for i in range(N):
    G.add_node(i+1)

for i in range(M):
    a,b = map(int, input().split())
    G.add_edge(a,b)
    
G2 = nx.to_scipy_sparse_matrix(G, nodelist=None, dtype=None, weight='weight', format='csr')
d,p = dijkstra(G2,indices = 0, return_predecessors=True)

print("Yes")
for i in range(1,N):
    print(p[i]+1)

### FIXED CODE ###

import math
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import networkx as nx

import heapq
import sys

input = sys.stdin.readline


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

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    path = [-1] * N
    for a,b in edge[s]:
        path[b] = s
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:                
            if used[e[1]]:
                if path[e[1]] == -1:
                    path[e[1]] = v
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d, path

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

for i in range(M):
    x,y = map(int,input().split())
    edge[x-1].append([1,y-1])
    edge[y-1].append([1,x-1]) 
    

d, path = dijkstra_heap(0, edge)

print("Yes")
for i in range(1,N):
    print(path[i]+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math

A, B, N = MII_split()

def f(x):
    return math.floor(A * x / B) - A * math.floor(x / B)

max = 0
for x in range(1, B + 1):
    if x > N:
        break
    fx = f(x)
    # print(fx)
    if fx > max:
        max = fx
print(max)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math

A, B, N = MII_split()

def f(x):
    return math.floor(A * x / B) - A * math.floor(x / B)

# max = 0
# for x in range(min(B + 1, N + 1)):
#     if x > N:
#         break
#     fx = f(x)
#     # print(fx)
#     if fx > max:
#         max = fx
print(f(min(B-1, N)))
### BUGGY CODE ###

a,b,c = map(int,input().split())
#if a == b == c:
#    print(-1)
#    exit()
for i in range(10**8):
    if a%2 != 0 or b%2 != 0 or c%2 != 0:
        break
    a_o,b_o,c_o = a,b,c
    a = b_o//2 + c_o//2
    b = a_o//2 + c_o//2
    c = a_o//2 + b_o//2
print(i)

### FIXED CODE ###

a,b,c = map(int,input().split())
if a == b == c and a%2 == 0:
    print(-1)
    exit()
for i in range(10**8):
    if a%2 != 0 or b%2 != 0 or c%2 != 0:
        break
    a_o,b_o,c_o = a,b,c
    a = b_o//2 + c_o//2
    b = a_o//2 + c_o//2
    c = a_o//2 + b_o//2
print(i)
### BUGGY CODE ###

N,M =[int(i)for i in input().split()]
ko =[[] for i in range(N)]
tyo =set([i for i in range(N)])
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    tyo = tyo - {B-1}
    ko[A-1].append(B-1)
tyo =list(tyo)
tyouten =tyo[0]
rank =[[-1,-1]for _ in range(N)]
def keisan(num,no,bef):
    if rank[num][0] < no:
        rank[num]=[no,bef+1]
    else:
        return
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
ans =""
for i in rank:
    ans =ans +str(i[1])+"\n"
print(ans)

### FIXED CODE ###

import queue
N,M =[int(i)for i in input().split()]
adlist =[[]for i in range(N)] #隣接リスト
oyalist =[[]for i in range(N)] #親ノードリスト
for _ in range(N+M-1):
    A,B =[int(i)-1 for i in input().split()]
    adlist[A].append(B)
    oyalist[B].append(A)

iri =[0]*N #入次数のリスト
for i in range(N):
    iri[i] =len(oyalist[i])

topo =[0]*N #トポロジカルソートの番号
tyouten =oyalist.index([]) #頂点
num = 0 #ソート番号
q =queue.Queue()
q.put(tyouten)
topo[tyouten]=num

while num != N-1:
    now = q.get()
    for i in adlist[now]:
        iri[i] -=1
        if iri[i] == 0:
            q.put(i)
            num += 1
            topo[i] =num

#出力
oyalist[tyouten].append(-1)
for i in range(N):
    oyalist[i] =sorted(oyalist[i],key=lambda x:topo[x],reverse=True)
    print(oyalist[i][0]+1)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
a=list(set(A))
for i in range(1,N+1):
    if i in a:
        print(A.count(i))
    else:
        print(0)

### FIXED CODE ###

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

N = int(input())
nums = [int(s) for s in input().rstrip().split()]
Q = int(input())

dct = {}
for k in range(N):
  n = nums[k]
  if n in dct:
    dct[n] += 1
  else:
    dct[n] = 1

for _ in range(Q):
  B, C =(int(s) for s in input().rstrip().split())
  if B in dct:
    if C in dct:
      dct[C] += dct.pop(B)
    else:
      dct[C] = dct.pop(B)

  sum = 0
  for k, v in dct.items():
    sum += k * v
  
  print(sum)


### FIXED CODE ###

from collections import defaultdict

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

res = 0

dct = defaultdict(int)
for _ in range(N):
  n = nums.pop()
  dct[n] += 1
  res += n

for _ in range(Q):
  B, C = map(int,input().split())
  if B in dct:
    n = dct.pop(B)
    res += (C - B) * n
    if C in dct:
      dct[C] += n
    else:
      dct[C] = n
  
  print(res)
### BUGGY CODE ###

import sys
from collections import Counter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = list(_ia())
    a.sort()
    c = Counter(a)
    w = set()
    o = []
    m = 10**6 + 1
    for ai in a:
        if ai in w:
            continue
        o.append(ai)
        for j in range(ai+ai, m, ai):
            w.add(j)

    cnt = 0
    for oi in o:
        if c[oi] == 1:
            cnt += 1
    return cnt


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


### FIXED CODE ###

import sys
from collections import Counter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = _i()
    a = Counter(_ia())
    k = sorted(a.keys())
    m = max(k) + 1
    c = [False for i in range(m)]
    cnt = 0
    for ki in k:
        if c[ki]:
            continue
        if a[ki] == 1:
            cnt += 1
        for j in range(ki+ki, m, ki):
            c[j] = True

    return cnt


if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    check[pos] = True
    ans[pos] += ans[before]
    for next_pos in root[pos]:
        if check[next_pos]:
            continue
        dfs(next_pos, pos)

check = [False for _ in range(n)]
dfs(0, -1)

for i in range(n):
    print(ans[i], end=" ")

### FIXED CODE ###

from sys import setrecursionlimit, stdin

setrecursionlimit(10 ** 9)

def input():
    return stdin.readline()

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    for next_pos in root[pos]:
        if next_pos == before:
            continue
        ans[next_pos] += ans[pos]
        dfs(next_pos, pos)

dfs(0, -1)

for i in range(n):
    print(ans[i], end=" ")
### BUGGY CODE ###

S = input()
RtoL = []
LtoR = []
for i in range(len(S)-1):
    if S[i] == 'R' and S[i+1] == 'L':
        RtoL.append(i+1)
    elif S[i] == 'L' and S[i+1] == 'R':
        LtoR.append(i+1)
LtoR.append(len(S))
LR_RL = []
for i in range(len(LtoR)):
    LR_RL.append(LtoR[i]-RtoL[i])
for i in range(len(LtoR)-1,0,-1):
    LtoR[i] = LtoR[i]-LtoR[i-1]
ans = [0]*len(S)
for i in range(len(RtoL)):
    k = LtoR[i]
    p = LtoR[i]//2
    z = RtoL[i]
    if k%2 ==0:
        ans[z] = p
        ans[z-1] = p
    else:
        if LR_RL[i]%2 == 0:
            ans[z] = p
            ans[z-1] = k-p
        else:
            ans[z] = k-p
            ans[z-1] = p
ans_str = ""
for i in range(len(ans)):
    ans_str += str(ans[i])
    ans_str += " "
    
print(ans_str[0:-1])

### FIXED CODE ###

S = input()
RtoL = []
LtoR = []
for i in range(len(S)-1):
    if S[i] == 'R' and S[i+1] == 'L':
        RtoL.append(i+1)
    elif S[i] == 'L' and S[i+1] == 'R':
        LtoR.append(i+1)
LtoR.append(len(S))
LR_RL = [0]*(len(LtoR))
ans = [0]*len(S)
for i in range(len(LtoR)-1,-1,-1):
    LR_RL[i] = LtoR[i]-RtoL[i]
    if i-1 > -1:
        LtoR[i] = LtoR[i]-LtoR[i-1]
    k = LtoR[i]
    p = LtoR[i]//2
    z = RtoL[i]
    if k%2 ==0:
        ans[z] = p
        ans[z-1] = p
    else:
        if LR_RL[i]%2 == 0:
            ans[z] = p
            ans[z-1] = k-p
        else:
            ans[z] = k-p
            ans[z-1] = p


ans_str = ""
for i in range(len(ans)):
    ans_str += str(ans[i])
    ans_str += " "
    
print(ans_str[0:-1])
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

A =sorted(A)

C = Counter(A)
ans=0
while A:
    d = A[0]
    if C[d]==1:
        ans+=1
    A = [a for a in A if a%d!=0]
print(ans)


### FIXED CODE ###

from collections import Counter
N =int(input())
A = list(map(int,input().split()))

A = sorted(A)
C = Counter(A)
S=set(A)

dp=[True]*(A[-1]+1)

ans=0
for i in range(1,A[-1]+1):
    if dp[i]:
        if i in S:
            for j in range(i,A[-1]+1,i):
                dp[j]=False
            if C[i]==1:
                ans+=1
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
ans=[0]*N
ans[1]=abs(h[1]-h[0])
for i in range(2,N):
    cost=[]
    for j in range(max(0,i-K),i):
        cost.append(abs(h[i]-h[j])+ans[j])
    ans[i]=min(cost)
print(ans[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

from collections import Counter

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

dup=0

for width in range(2000):
    for i in range(N):
        try:
            if set((S[i],S[i+width],S[i+width*2]))==set(('R','G','B')):
                dup+=1
        except IndexError:
            break

c=Counter(S)
retval=c['R']*c['G']*c['B']-dup
print(retval)


### FIXED CODE ###

from collections import Counter

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

dup=0
RGB=set(('R','G','B'))

for width in range(N//2+10):
    for i in range(N):
        try:
            if set((S[i],S[i+width],S[i+width*2]))==RGB:
                dup+=1
        except IndexError:
            break

c=Counter(S)
retval=c['R']*c['G']*c['B']-dup
print(retval)
### BUGGY CODE ###

from heapq import heappush, heappop
from math import sqrt
xs, ys, xt, yt = map(int, input().split())
N = int(input())
C = [list(map(int, input().split())) for i in range(N)]

que = []
dist = [10**18]*N
used = [0]*N
for i, (x, y, r) in enumerate(C):
    d0 = (xs - x)**2 + (ys - y)**2
    r0 = sqrt(d0) - r if d0 > r**2 else 0
    dist[i] = r0
    heappush(que, (r0, i))

while que:
    c, i = heappop(que)
    if used[i]:
        continue
    xi, yi, ri = C[i]
    used[i] = 1
    d = dist[i]
    for j, (x, y, r) in enumerate(C):
        if used[j]:
            continue
        d0 = (xi - x)**2 + (yi - y)**2
        r0 = sqrt(d0) - ri - r if d0 > (ri + r)**2 else 0
        if d + r0 < dist[j]:
            dist[j] = v = d + r0
            heappush(que, (v, j))
ans = sqrt((xs - xt) ** 2 + (ys - yt) ** 2)
for i, (x, y, r) in enumerate(C):
    d0 = (xt - x)**2 + (yt - y)**2
    r0 = sqrt(d0) - r if d0 > r**2 else 0
    ans = min(ans, dist[i] + r0)
print("%.16f" % ans)

### FIXED CODE ###

from heapq import heappush, heappop
from math import sqrt
xs, ys, xt, yt = map(int, raw_input().split())
n = input()
ps = [map(int, raw_input().split()) for i in xrange(n)]
cant = [0]*n
for i in xrange(n):
    x0, y0, r0 = ps[i]
    for j in xrange(n):
        x1, y1, r1 = ps[j]
        if i == j or r0 > r1: continue
        if (x0 - x1)**2 + (y0 - y1)**2 <= (r1 - r0)**2:
            cant[i] = 1
            break

EPS = 1e-10
que = []
dist = [10**18+7]*n
def calc(x0, y0, r0, x1, y1, r1):
    v = (x0 - x1)**2 + (y0 - y1)**2
    if v <= (r0+r1)**2:
        return 0.
    return sqrt(v) - r0 - r1
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = dist[i] = calc(xs, ys, 0, x, y, r)
    heappush(que, (d, i))
while que:
    d, v = heappop(que)
    if dist[v] < d:
        continue
    x0, y0, r0 = ps[v]
    for t in xrange(n):
        if v == t or cant[t]: continue
        x1, y1, r1 = ps[t]
        nd = calc(x0, y0, r0, x1, y1, r1)
        if d+nd < dist[t]:
            dist[t] = d+nd
            heappush(que, (d+nd, t))
ans = sqrt((xs - xt)**2 + (ys - yt)**2)
for i in xrange(n):
    if cant[i]: continue
    x, y, r = ps[i]
    d = calc(xt, yt, 0, x, y, r) + dist[i]
    ans = min(ans, d)
print "%.010f" % ans
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

def enumerate_factor(x):
    i = 1
    factors = []
    while i * i <= x:
        if x % i == 0:
            factors.append(i)
            if x // i != i:
                factors.append(x // i)
        i += 1
    return factors

def main():
    x = read(int)
    
    boundary = math.ceil(math.pow(x, 1/5))
    for factor in enumerate_factor(x):
        for b in range(-boundary - factor, boundary + factor + 1):
            a = b + factor
            if a**5 - b**5 == x:
                print(f"{a} {b}")
                return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

def enumerate_factor(x):
    i = 1
    factors = []
    while i * i <= x:
        if x % i == 0:
            factors.append(i)
            if x // i != i:
                factors.append(x // i)
        i += 1
    return factors

def main():
    x = read(int)
    
    boundary = math.ceil(math.pow(x, 1/5))
    for factor in enumerate_factor(x):
        f = math.ceil(math.pow(factor, 1/5))
        for b in range(-boundary * 10, boundary * 10):
            a = b + factor
            if a**5 - b**5 == x:
                print(f"{a} {b}")
                return
            a = b - factor
            if a**5 - b**5 == x:
                print(f"{a} {b}")
                return

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

from collections import deque

S = input()
Q = int(input())

q = deque(S)

for i in range(Q):
    T = input().split()
    if len(T) == 1:
        q.reverse()
    else:
        F = int(T[1])
        C = T[2]
        if F == 1:
            q.appendleft(C)
        else:
            q.append(C)

print(''.join(q))


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

q = deque(S)

parity = 0
for i in range(Q):
    T = input().split()
    if len(T) == 1:
        parity = (parity + 1) % 2
        #q.reverse()
    else:
        F = int(T[1])
        C = T[2]

        if parity == 0:
            if F == 1:
                q.appendleft(C)
            else:
                q.append(C)
        else:
            if F == 1:
                q.append(C)
            else:
                q.appendleft(C)

if parity == 1:
    q.reverse()

print(''.join(q))
### BUGGY CODE ###

import functools
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
maxV = max(vs)
V = maxV * N
INF = 10**10

dp = {}
def minweight(i, v):
    if (i, v) not in dp:
        if i == 0:
            if v == 0: dp[i, v] = 0
            elif v == vs[i]: dp[i, v] = ws[i]
            else: dp[i, v] = INF
        else:
            if vs[i] <= v:
                dp[i, v] = min(minweight(i - 1, v - vs[i]) + ws[i], minweight(i - 1, v))
            else:
                dp[i, v] = minweight(i - 1, v)
    return dp[i, v]

for v in range(V, -1, -1):
    if minweight(N - 1, v) <= W:
        print(v)
        break

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
INF = 10**13

def maxvalue_dp(ws, vs, W):
    V = sum(vs)
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    for w, v in zip(ws, vs):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

print(maxvalue_dp(ws, vs, W))