Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A,reverse=True)
bc = []
for i in range(M):
    bc.append(list(map(int,input().split())))

bc = sorted(bc,key=lambda x : x[1],reverse=True)

import bisect
ans = 0
c = 0
for i in range(M):
    if A[-bc[i][0]-c] > bc[i][1]:
        cc = bisect.bisect_left(sorted(A),bc[i][1])
        ans += (bc[i][1]*(cc-c))
        c += (cc-c)
        break
    else:
        c += bc[i][0]
        ans += (bc[i][1]*bc[i][0])

for i in range(N):
    if i < N - c:
        ans += A[i]
    else:
        break

print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
bc = []
for i in range(M):
    bc.append(list(map(int,input().split())))

bc = sorted(bc,key=lambda x : -x[1])
i = 0
for b,c in bc:
    for j in range(i,min(N,i+b)):
        if A[j] < c:
            A[j] = c
    i += b
print(sum(A))
a=int(input())
b=list(input())
c=0
for i in range(a):
  if b[i]=="A":
    if b[i+1]=="B":
    else:
      pass
      if b[i+2]=="C":
        c+=1
  else:
    pass
print(c)


### FIXED CODE ###

n=int(input())
s=list(input())
d=0
for i in range(n):
  if n-(i+1)>=2:
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      d+=1
  else:
    pass
print(d)
A = [0 for _ in xrange(10**5+10)]
    N, K = map(int, raw_input().split())
    for i in xrange(N):
        a, b = map(int, raw_input().split())
        A[a] += b
     
    k = 0
    for i in xrange(10**5+10):
        k += A[i]
        if k >= K:
            print i
            break

### FIXED CODE ###

A = [0 for _ in xrange(10**5+10)]
N, K = map(int, raw_input().split())
for i in xrange(N):
    a, b = map(int, raw_input().split())
    A[a] += b

k = 0
for i in xrange(10**5+10):
    k += A[i]
    if k >= K:
        print i
        break
a = input()
b = 1
while(a = NULL):
	print("Case " + str(i) + ": " + str(a))

### FIXED CODE ###

a = int(input())
b = 1
while(a != 0):
	print("Case " + str(b) + ": " + str(a))
	b = b + 1
	a = int(input())
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
A=[list(map(int,input().split())) for _ in range(N)]
cnt=0
for a in A:
  ans=C
  for i in range(M):
    ans+=a[i]*B[i]
  if ans>0:
    cnt+=1
print(cnt)

### FIXED CODE ###

H,W=map(int,input().split())
h,w=map(int,input().split())
print((H-h)*(W-w))
n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A,B = [0],[0]
 
for i in range(n):
  A.append(a[i] + A[i])
for i in range(m):
  B.append(b[i] + B[i])
 
num,x = 0,m-1
A.pop(0)
B.pop(0)
 
for i in range(len(A)):
  if A[i] > k:
    break
  while A[i] + B[x] > k:
    x -= 1
  num = max(num, i + x + 2)
  
print(num)


### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A,B = [0],[0]

for i in range(n):
  A.append(a[i] + A[i])
for i in range(m):
  B.append(b[i] + B[i])

num,x = 0,m

for i in range(n+1):
  if A[i] > k:
    break
  while A[i] + B[x] > k:
    x -= 1
  num = max(num, i + x)
  
print(num)
L, L+1, L+2, ..., L+N-1
N, L = list(map(lambda x: int(x), input().split(" ")))

S = int(N * (N-1) / 2) + L * N

if L >= 0:
  print(S - L)
elif L + N - 1 <= 0:
  print(S - L - N + 1)
else:
  print(S)

### FIXED CODE ###

N, L = list(map(lambda x: int(x), input().split(" ")))
 
S = int(N * (N-1) / 2) + L * N
 
if L >= 0:
  print(S - L)
elif L + N - 1 <= 0:
  print(S - L - N + 1)
else:
  print(S)
a=int(input())
b=int(input())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
# import
import numpy as np
import sys
sys.setrecursionlimit(10**6)

# input
H, W = map(int, input().split())

Mtmp = []
for _ in range(H):
    tmp = list(input())
    Mtmp.append(tmp)

M = np.array(Mtmp)
S = np.array([[0]*W]*H)

print(M)

digtmp = np.array([[0, 1], [1, 0], [0, -1], [-1, 0]])

def dfs(i, j):
    global ngflag
    global searchflag
    if S[i, j] == 1:
        return
    S[i, j] = 1
    if M[i, j] == '.':
        return
    print("i:{}, j:{}".format(i, j))
    searchflag = 1
    dig = digtmp + np.array([i, j])
    for d in dig:
        if 0 <= d[0] < H and 0 <= d[1] < W:
            if M[d[0], d[1]] == '#':
                ngflag = 0
                dfs(d[0], d[1])

searchflag = 0
ngflag = 1

while True:
    if 0 not in S:
        if M[target[0], target[1]] == '.':
            ngflag = 0
        break
    target = list(zip(*np.where(S == 0)))[0]
    print("sf:{}, ng:{}".format(searchflag, ngflag))
    if M[target[0], target[1]] == '#':
        ngflag = 1
    dfs(target[0], target[1])
    if M[target[0], target[1]] == '#' and searchflag == 1 and ngflag == 1:
        break


print("sf:{}, ng:{}".format(searchflag, ngflag))

if searchflag == 1 and ngflag == 0:
    ans = 'Yes'
elif searchflag == 1 and ngflag == 1:
    ans = 'No'
else:
    ans = 'Yes'

print(ans)


### FIXED CODE ###


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

if a <= b:
    ans = a
else:
    ans = a-1

print(ans)
a,b = [float(i) for i in input().split()]
d = int(a/b)
r = int(a) % int(b)
f = a/b
f = round(decimal.Decimal(f), 10)
print(str(d) + " " + str(r) + " " + str(f))


### FIXED CODE ###

a,b = [float(i) for i in input().split()]
d = int(a/b)
r = int(a) % int(b)
f = a/b
f = "{:.6f}".format(f)

print(d,r,f)
a = int(input())
b = int(input())
if a<=8 and b <= 8:
    print("Yay!")
else:
    print(":(")

### FIXED CODE ###

a, b = map(int,input().split())
if a<=8 and b <= 8:
    print("Yay!")
else:
    print(":(")
def getMinCost(arr,i,n,cache):
    if i > n-2:
        return 0
    if cache[i] != float("inf"): return cache[i]
    op1 = abs(arr[i] - arr[i+1]) + getMinCost(arr,i+1,n,cache)
    op2 = abs(arr[i] - arr[i+2]) + getMinCost(arr,i+2,n,cache) if i != n-2 else float("inf")
    cache[i] = min(op1,op2)
    return cache[i]

n = int(input())
arr = [int(i) for i in input().split()]
cache = [float("inf") for i in range(n)]
print(getMinCost(arr,0,n,cache))


### FIXED CODE ###

n = int(input())
arr = [int(i) for i in input().split()]
dp = [0 for i in range(n)]
for i in range(1,n):
    op1 = abs(arr[i]-arr[i-1]) + dp[i-1]
    op2 = abs(arr[i]-arr[i-2]) + dp[i-2] if i != 1 else float("inf")
    dp[i] = min(op1,op2)
print(dp[n-1])
a,p = map(int,input().split())
print((a*3+p)//2)

### FIXED CODE ###

n = int(input())
print(180*(n-2))
import numpy as np
argList = list(map(int, input().split())) 
heights = list(map(int, input().split())) 

#いい展望台フラグ
check = np.array([1]*argList[0])

for n in range(argList[0]-1):
    #どことどこをつないでいるか
    con = list(map(int, input().split())) 
    #print(con)
    #低かったらいい展望台ではない
    if heights[con[0]-1] < heights[con[1]-1]:
        check[con[0]-1] = 0
    else:
        check[con[1]-1] = 0
print(np.sum(check))

### FIXED CODE ###

import numpy as np
argList = list(map(int, input().split())) 
heights = list(map(int, input().split())) 

#いい展望台フラグ
check = np.array([1]*argList[0])

for n in range(argList[1]):
    #どことどこをつないでいるか
    con = list(map(int, input().split())) 
    #低かったらいい展望台ではない
    if heights[con[0]-1] <= heights[con[1]-1]:
        check[con[0]-1] = 0
    if heights[con[0]-1] >= heights[con[1]-1]:
        check[con[1]-1] = 0
print(np.sum(check))
import sys

def is_onepair(x):
    for i in range(4):
        if x.count(x[i]) == 2:
            return True

    return False

def is_twopair(x):
    count = 0
    for e in x:
        for e2 in x:
            if e == e2:
                count += 1
            if count == 2:
                return True

    return False

def is_threecard(x):
    for i in range(3):
        if x.count(x[i]) == 3:
            return True

    return False

def is_straight(x):
    x.sort()
    if x[0] == 1 and x[1:] = [10, 11, 12, 13]:
        return True
    for i in range(4):
        if x[i]+1 != x[i+1]:
            return False
    
    return True

def is_fullhouse(x):
    if is_threecard(x) and is_onepair(x):
        return True

    return False
    
def is_fourcard(x):
    for i in range(2):
        if x.count(x[i]) == 4:
            return True

    return False

for line in sys.stdin.readlines():
    hand = list(map(int, line.split(',')))
    if is_fourcard(hand):
        print("four card")
    elif is_fullhouse(hand):
        print("full house")
    elif is_straight(hand):
        print("straight")
    elif is_threecard(hand):
        print("three card")
    elif is_twopair(hand):
        print("two pair")
    elif is_onepair(hand):
        print("one pair")
    else:
        print("null")

### FIXED CODE ###

import sys

def is_onepair(x):
    for i in range(4):
        if x.count(x[i]) == 2:
            return True

    return False

def is_twopair(x):
    count = 0
    i = 0
    x.sort()
    while i < 5:
        if x.count(x[i]) == 2:
            i += 2
            count += 1
        else:
            i += 1
        if count == 2:
            return True

    return False

def is_threecard(x):
    for i in range(3):
        if x.count(x[i]) == 3:
            return True

    return False

def is_straight(x):
    x.sort()
    if x[0] == 1 and x[1:] == [10, 11, 12, 13]:
        return True
    for i in range(4):
        if x[i]+1 != x[i+1]:
            return False
    
    return True

def is_fullhouse(x):
    if is_threecard(x) and is_onepair(x):
        return True

    return False
    
def is_fourcard(x):
    for i in range(2):
        if x.count(x[i]) == 4:
            return True

    return False

for line in sys.stdin.readlines():
    hand = list(map(int, line.split(',')))
    if is_fourcard(hand):
        print("four card")
    elif is_fullhouse(hand):
        print("full house")
    elif is_straight(hand):
        print("straight")
    elif is_threecard(hand):
        print("three card")
    elif is_twopair(hand):
        print("two pair")
    elif is_onepair(hand):
        print("one pair")
    else:
        print("null")
N,X = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
L = []

if (len(x) == 1):
  print(abs(X-x[0]))
else:
  L.append(abs(X-x[0]))
  for k in range(len(x)):
    p = abs(X-x[k])
    if (p < L[0]):
      del L[0]
      L.append(p)
print(L[0])

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
for i in range(N):
  L[i] = abs(L[i]-X)
L.sort()
L.reverse()
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b,a%b)
def listgcd(L):
  p = L[0]
  for i in range(1,N):
    p = gcd(p,L[i])
  return p
if len(L) >= 2:
  print(listgcd(L))
else:
  print(L[0])
import sys
n = int(input())
h = list(map(int,input().split()))
d = [0]*(n-1)

for i in range(n-1):
  d[i]= h[i+1]-h[i]

sd = sorted(d)
if min(sd) <= -2:
  print("No")
  sys.exit()
  
elif -1 in d:
  indexes = [i for i, x in enumerate(d) if x == -1]
  for j in range(len(indexes)-1):
    if d[j+1] != 0:
      print("No")
      sys.exit()

print("Yes")
  

### FIXED CODE ###

import sys
n = int(input())
h = list(map(int,input().split()))
mi = h[0]-1
if n == 1:
  print("Yes")
  sys.exit()
  
for i in range(1,n):
  if h[i-1]-1 == h[i]:
    if mi > h[i]:
      print("No")
      sys.exit()
    mi = h[i]
  elif h[i-1] > h[i]:
    print("No")
    sys.exit()
    
print("Yes")
N = str(input())

if N[-1] = "7" or N[-2] = "7" or N[-3] = "7":
    print("Yes")
else:
  	print("No")

### FIXED CODE ###

N = str(input())

if N[-1] == "7" or N[-2] == "7" or N[-3] == "7":
    print("Yes")
else:
  	print("No")
n, q = map(int, input().split())
d = {}
v = {}
for _ in range(n - 1):
    a, b = input().split()
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
    if b not in d:
        d[b] = []

for key in d.keys():
    v[key] = 0

for _ in range(q):
    node, increment = input().split()
    queue = [node]
    all_childs = [node]
    while len(queue) > 0:
        el = queue.pop()
        if el not in all_childs:
            all_childs.append(el)
        childs = d[el]
        if len(childs) > 0:
            queue.extend(d[el])
    for child in all_childs:
        v[child] += int(increment)

for value in v.values():
    print(value, end=' ')
print('')

### FIXED CODE ###

a = int(input())
s = input()
if a < 3200:
    print('red')
else:
    print(s)
L[0]+=2
  elif L[2]-L[1]>=2:
    L[1]+=2
  elif L[0] !=L[1] or L[1] !=L[2]:
    L[0]+=1
    L[1]+=1
  cnt+=1
  L.sort()
  if L[0]==L[1]==L[2]:
    break
print(cnt) 
    
    


### FIXED CODE ###

import sys
L=list(map(int,sys.stdin.readline().split()))
cnt=0
while True:
  if L[0]==L[1]==L[2]:
    break
  L.sort()
  if L[2]-L[0]>=2:
    L[0]+=2
  elif L[2]-L[1]>=2:
    L[1]+=2
  elif L[0] !=L[1] or L[1] !=L[2]:
    L[0]+=1
    L[1]+=1
  cnt+=1
  
print(cnt)
import math, sys

#??°????????????????????§????¨????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x, y)
    elif cmd == 1:
        print(ST.getsum(x,y + 1, right = ST.TreeRange))

### FIXED CODE ###

import math, sys

#??°????????????????????§????°????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x - 1, y)
    elif cmd == 1:
        print(ST.getsum(x - 1,y , right = ST.TreeRange))
a = int(inut())

print(a**3+a**2+a)

### FIXED CODE ###

a = int(input())

print(a**3+a**2+a)
import math
n = int(input())
a = list(map(int,input().split()))
li = []
li2 = []
for i in range(n-1):
    li.append(math.gcd(a[i],a[i+1]))
for i in range(n-2):
    li2.append(math.gcd(a[i],a[i+2]))
li = set(li)  | set(li2)
ans = max(li)
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
rs, ls = [0], [0]
for i in range(n-1):
    rs.append(gcd(rs[i], a[i]))
    ls.append(gcd(ls[i], a[-i-1]))
gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))
N, X = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
ans = 0
for i in A:
  ans += i
  if ans <= X:
    cnt += 1    
print(cnt)


### FIXED CODE ###

X, A = map(int, input().split())
if X < A:
  print(0)
else:
  print(10)
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


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

print(gcd_list(A))

### FIXED CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


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

print(gcd_list(A))
N=int(input)
A=list(int(input().split()))
ans=0
flag=True
if flag==True:
    for i in range(N)
        if A[i]%2==0:
            A[i]=A[i]/2
        else:
            flag=False
            break
    ans+=1
else:
    break
        
print(ans)

### FIXED CODE ###

sss=list(input())
print(sss.count('1'))
S == input()
if S = "ABC":
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if abs(A-B) - (V-W)*T <= 0:
  print("YES")
elif A==B:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

print(input()[:3])
# coding: utf-8
import sys
from fractions import gcd
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

@lru_cache(None)
def solve(index, n, g):
    '''既に１つ数を選んだらnは１'''
    if index == N:
        return g
    if n == 1:
        return solve(index+1, 1, gcd(g, A[index]))
    else:
        ret = max(solve(index+1, 1, g), solve(index+1, 0, gcd(g, A[index])))
        return ret

result1 = solve(0, 0,  A[0])
result2 = solve(0, 0, A[-1])
answer = max(result1, result2)
print(answer)


### FIXED CODE ###

from fractions import gcd
import math
N = int(input())
A = list(map(int, input().split()))

gl = [0] * (N-1)
gr = [0] * (N-1)

gl[0] = A[0]
gr[0] = A[-1]
for i in range(1,N-1):
    gl[i] = gcd(gl[i-1],A[i])
    gr[i] = gcd(gr[i-1],A[-i-1])
#print(gl[i])
ans = max(gr[-1],gl[N-2])
for i in range(1,N-1):
    g = gcd(gl[i-1],gr[-i-1])
    ans = max(ans,g)
#print(gl,gr)
print(ans)
H, W, M = map(int, input().split())
m = [[False] * W for _ in range(H)]
dh = dict()
dw = dict()
for _ in range(M):
    h_, w_ = map(int, input().split())
    m[h_ - 1][w_ - 1] = True
    
    if h_ in dh:
        dh[h_] += 1
    else:
        dh[h_] = 1
        
    if w_ in dw:
        dw[w_] += 1
    else:
        dw[w_] = 1

dhl = list(dh.items())
dhl.sort(key=lambda x: x[1], reverse=True)
dwl = list(dw.items())
dwl.sort(key=lambda x: x[1], reverse=True)

h, w = [], []
maxh = dhl[0][1]
maxw = dwl[0][1]

for i, n in dhl:
    if n == maxh:
        h.append(i)
for i, n in dwl:
    if n == maxw:
        w.append(i)

res = maxh + maxw - 1
for hh in h:
    for ww in w:
        if m[hh - 1][ww - 1] is False:
            res = maxh + maxw
            break

print(res)


### FIXED CODE ###

H, W, M = map(int, input().split())
row = [0] * (H + 1)
col = [0] * (W + 1)

bom = []
for i in range(M):
    h, w = map(int, input().split())
    bom.append([h, w])
    row[h] += 1
    col[w] += 1
 
rmax = max(row)
cmax = max(col)
cnt = row.count(rmax) * col.count(cmax)

for h, w in bom:
    if rmax == row[h] and cmax == col[w]:
        cnt -= 1

print(rmax + cmax - (cnt == 0))
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    m = 10**6

    a = [inf] * m
    b = [inf] * m
    a[0] = 0
    b[0] = 0
    for i in range(1,200):
        t = i * (i+1) * (i+2) // 6
        for j in range(t,m):
            if a[j] > a[j-t] + 1:
                a[j] = a[j-t] + 1
        if t % 2 == 0:
            continue
        for j in range(t,m):
            if b[j] > b[j-t] + 1:
                b[j] = b[j-t] + 1

    while True:
        n = I()
        if n == 0:
            break
        rr.append('{} {}'.format(a[n],b[n]))



    return '\n'.join(map(str, rr))


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    m = 10**6

    a = [inf] * m
    b = [inf] * m
    a[0] = 0
    b[0] = 0
    for i in range(1,200):
        t = i * (i+1) * (i+2) // 6
        mm = min(t*5,m)
        for j in range(t,mm):
            if a[j] > a[j-t] + 1:
                a[j] = a[j-t] + 1
        if t % 2 == 0:
            continue
        for j in range(t,m):
            if b[j] > b[j-t] + 1:
                b[j] = b[j-t] + 1

    while True:
        n = I()
        if n == 0:
            break
        rr.append('{} {}'.format(a[n],b[n]))



    return '\n'.join(map(str, rr))


print(main())
az = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
sum_az = [0 for x in range(26)]

while True:
    x = raw_input()
    x.lower()
    for i in range(26):
        for j in range(len(x)):
            if x[j] == az[i]:
                sum_az[i] += 1
    if x is None:
        break

for i in range(26):
    print ("%s : %d" % (az[i], sum_az[i]))
                

### FIXED CODE ###

import sys
az =["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
sum_az = [0 for x in range(26)]

for x in sys.stdin.read().lower():
    for i in range(26):
        if x == az[i]:
            sum_az[i] += 1


for i in range(26):
    print ("%s : %d" % (az[i], sum_az[i]))
s = input()

count = 1

for i in range(1, len(s)):
    ss = s[0:i]
    # print(ss, s[i])

    n = len(ss) - ss.count(s[i])
    count += n
    # print(n, count)
print(n)


### FIXED CODE ###

s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    for char, char_count in alphabets.items():
        if char != s[i]:
            count += char_count

    if s[i] in alphabets:
        alphabets[s[i]] += 1
    else:
        alphabets[s[i]] = 1

print(count)
X=int(input())
for i in range(-150,151):
    for j in range(-150,151):
        if i**5-j**5==X:
            print(i,j)
            exit()

### FIXED CODE ###

a = input()
if a == 'ABC': print('ARC')
else: print('ABC')
N=int(input())
h=list(map(int,input().split()))
memo=[-1]*(N+1)
def a(j):
    if j==0:
        return 0
    elif j==1:
        return abs(h[1]-h[0])
    else:
        if memo[j]==-1:
            memo[j]=min(a(j-1)+abs(h[j]-h[j-1]),a(j-2)+abs(h[j]-h[j-2]))
        return memo[j]
print(a(N-1))

### FIXED CODE ###

N=int(input())
h=list(map(int,input().split()))
a=[0]*N
for j in range(1,N):
    if j==1:
        a[1]=a[0]+abs(h[1]-h[0])
    else:
        a[j]=min(a[j-1]+abs(h[j]-h[j-1]),a[j-2]+abs(h[j]-h[j-2]))
print(a[-1])
import sys
M=input()

for i in range(l0):
  if(M.find(str(i))!=-1):
    print("Yes")
    sys.exit()
print("No")

### FIXED CODE ###

import sys
M=input()
 
for i in range(10):
  if(M.find(str(i)*3)!=-1):
    print("Yes")
    sys.exit()
print("No")