CodeEff/ECCO huggingface dataset:
# Original solution
N, *A = [int(_) for _ in open(0).read().split()]
win_lose = {i: set() for i in range(1, N + 1)}
for win, lose in zip(A, list(range(2, N + 1))):
    win_lose[win].add(lose)
s1 = [1]
s2 = []
while s1:
    a = s1.pop()
    s2 += [a]
    for b in win_lose[a]:
        s1 += [b]
dp = [0] * (N + 1)
for x in s2[::-1]:
    if win_lose[x] == set():
        dp[x] = 0
    else:
        dp[x] = max(a + b for a, b in zip(
            sorted(dp[y] for y in win_lose[x])[::-1], list(range(1, N + 1))))
print((dp[1]))


# Optimized solution
N, *A = [int(_) for _ in open(0).read().split()]
win_lose = {i: set() for i in range(1, N + 1)}
for win, lose in zip(A, list(range(2, N + 1))):
    win_lose[win].add(lose)
s1 = [1]
s2 = []
while s1:
    a = s1.pop()
    s2 += [a]
    for b in win_lose[a]:
        s1 += [b]
dp = [0] * (N + 1)
for x in s2[::-1]:
    if win_lose[x] == set():
        dp[x] = 0
    else:
        dp[x] = max(
            i + v + 1
            for i, v in enumerate(sorted(dp[y] for y in win_lose[x])[::-1]))
print((dp[1]))
# Original solution

def myAnswer(N:int)->int:
   K = len(str(N)) #桁数
   if(K == 1):return N
   c = N // 10**(K-1) #最上位の桁の数
   if((c*10**(K-1) + int("9"*(K-1)))<= N):
      return c + 9 *(K - 1)
   else:
      return c + 9 *(K - 1) -1 


def modelAnswer():
   tmp=1
def main():
   N = int(eval(input()))
   print((myAnswer(N)))

if __name__ == '__main__':
   main()

# Optimized solution
def myAnswer(N:int)->int:
   length = len(str(N))
   if(length == 1): return N
   l = list(str(N))
   tmp = 0
   for n in l[1:]:
      tmp += int(n)
   total = length * 9
   if(tmp == total - 9):
      return tmp + int(l[0])
   else:
      total += -9 + int(l[0]) - 1
      return total
def modelAnswer():
   tmp=1
def main():
   N = int(eval(input()))
   print((myAnswer(N)))

if __name__ == '__main__':
   main()
# Original solution
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

s = ins()


def solve():
    ans = 9 * (len(s) - 1)
    x = [int(d) for d in s]
    sx = sum(x)
    ans = max(ans, sx)
    ans = max(ans, (x[0] - 1) + 9 * (len(s) - 1))
    return ans


print(solve())


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

X = ins()


def solve():
    ans = sum([int(d) for d in X])

    ans = max(ans, int(X[0]) - 1 + 9 * (len(X) - 1))

    return ans


print(solve())
# Original solution
import math
n=int(eval(input()))
s = str(n)
array = list(map(int, list(s)))
a1=sum(array)
size = int (math.log10(n))
a2=int(n/(10**size))-1+size*9
print((max(a1,a2)))


# Optimized solution
n = int(eval(input()))
c = None
res = 0
for i in range(1, len(str(n))+1):
    c = '9' * i
    if int(c) <= n:
        continue
    else:
        for j in range(9, -1, -1):
            if int(str(j) + str(c)[1:]) <= n:
                c = str(j) + str(c)[1:]
                break
        break
for i in range(len(c)):
    res += int(c[i])
print(res)
# Original solution
n = int(eval(input()))

def digit_sum_simple(n):
    
    max_sum = -1

    for i in range(10**(len(str(n))-1)-1, n+1):
        
        i_parts = []
        for i_part in str(i):
            i_parts.append(int(i_part))

        this_sum = sum(i_parts)
        
        if max_sum < this_sum:
            max_sum = this_sum
            max_sum_i = i

    return max_sum, max_sum_i

def digit_sum_temp(n):
    max_sum_i = int(str(int(str(n+1)[0])-1) + "9"*(len(str(n+1))-1))
    max_sum = sum([int(j) for j in str(max_sum_i)])

    return max_sum

print((digit_sum_temp(n)))

# Optimized solution
n = int(eval(input()))
print((sum([int(j) for j in str(int(str(n+1)[0])-1) + "9"*(len(str(n+1))-1)])))
# Original solution
N = int(eval(input()))
keta = len(str(N))
SN = str(N)
if N <= 9:
    print(N)
elif SN.count('9') == keta:
    print((9*keta))
elif SN.count('9') == keta-1 and SN[0] != '9':
    print(((keta - 1) * 9 + int(SN[0])))
else:
    print(((keta - 1) * 9 + int(SN[0])-1))

# Optimized solution
n=int(eval(input()))
k=len(str(n))
c=n//10**(k-1)
print((c+9*(k-1) if n==(c+1)*10**(k-1)-1 else c+9*(k-1)-1))
# Original solution
n=int(eval(input()))
a=int(eval(input()))
if((n%500) <= a):
    print('Yes')
else:
    print('No')



# Optimized solution
n=int(eval(input()))
a=int(eval(input()))
n%=500
if(n<=a):
    print('Yes')
else:
    print('No')
# Original solution
N = int(eval(input()))
A = int(eval(input()))

for i in range(A+1):
    if (N-i)%500==0:
        print('Yes')
        break
else:
    print('No')

# Optimized solution
N = int(eval(input()))
A = int(eval(input()))
print(('Yes' if N%500<=A else 'No'))
# Original solution
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    def main():
        n=int(eval(input()))
        a=int(eval(input()))
        for i in range(21):
            for j in range(a+1):
                if 500*i+1*j==n:
                    return 'Yes'
        return 'No'
    print((main()))
resolve()

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(eval(input()))
    a=int(eval(input()))
    if n%500>a:
        print('No')
    else:
        print('Yes')
resolve()
# Original solution
n = int(eval(input()))
a = int(eval(input()))
if (n % 500) <= a:
    print("Yes")
else:
    print("No")

# Optimized solution
print(("Yes" if int(eval(input()))%500<=int(eval(input())) else "No"))
# Original solution
N = int(eval(input()))  # total payment amount
A = int(eval(input()))  # the amount of 1 Yen

kozeni = N % 500
if kozeni <= A:
    print("Yes")
else:
    print("No")


# Optimized solution
N = int(eval(input()))
A = int(eval(input()))

if (N % 500) <= A:
    print("Yes")
else:
    print("No")
# Original solution
n=int(eval(input()))
a=int(eval(input()))
print(('YNeos'[n%500>a::2]))

# Optimized solution
print(('YNeos'[int(eval(input()))%500>int(eval(input()))::2]))
# Original solution
# coding: utf-8
# Your code here!

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

if N%500<=S:
    print("Yes")
else:
    print("No")

# Optimized solution
# coding: utf-8
# Your code here!
N = int(eval(input()))
A = int(eval(input()))

if N%500 <= A:
    print("Yes")
else: 
    print("No")
# Original solution
n = int(eval(input()))
a = int(eval(input()))

m = n % 500
if m <= a:
    print('Yes')
else:
    print('No')

# Optimized solution
n = int(eval(input()))
a = int(eval(input()))
if n % 500 <= a:
    print('Yes')
else:
    print('No')
# Original solution
print(('Yes' if int(eval(input()))%500<=int(eval(input())) else 'No'))


# Optimized solution
if int(eval(input()))%500<=int(eval(input())):
  print("Yes")
else:
  print("No")
# Original solution
n = int(eval(input()))
a = int(eval(input()))
if n%500 <= a:
  print("Yes")
else:
  print("No")

# Optimized solution
n = int(eval(input()))
a = int(eval(input()))
print(("Yes" if n%500 <= a else "No"))
# Original solution
N = int(eval(input()))
A = int(eval(input()))

if N % 500 <= A:
    print("Yes")
else:
    print("No")

# Optimized solution
N = int(eval(input()))
A = int(eval(input()))

print((["Yes", "No"][N % 500 > A]))
# Original solution
n=int(eval(input()))%500
print(('No' if n>int(eval(input())) else 'Yes'))

# Optimized solution
print(('No'if int(eval(input()))%500>int(eval(input()))else'Yes'))
# Original solution
n = int(eval(input()))
a = int(eval(input()))

q = n % 500

if a >= q:
  print('Yes')
else:
  print('No')

# Optimized solution
n =int(eval(input()))
a =int(eval(input()))
print(('Yes' if n %500<=a else 'No'))
# Original solution
n = int(eval(input()))
a = int(eval(input()))

res = n%500
if res <= a:
  print('Yes')
else:
  print('No')

# Optimized solution
n = int(eval(input()))
a = int(eval(input()))

n -= (n//500)*500
if n<=a:
  print('Yes')
else:
  print('No')
# Original solution
n = int(eval(input()))
a = int(eval(input()))

flg = False
for i in range(a+1):
    if (n-i) % 500 == 0:
        flg = True
        break

if flg:
    print("Yes")
else:
    print("No")



# Optimized solution
n = int(eval(input()))
a = int(eval(input()))

if n % 500 <= a:
    print("Yes")
else:
    print("No")
# Original solution
a = int(eval(input()))
b = int(eval(input()))
a = a % 500
if a > b:
 print("No")
else:
 print("Yes")

# Optimized solution
n = int(eval(input()))
a = int(eval(input()))
n %= 500
if n <= a:
  print("Yes")
else:
  print("No")
# Original solution
N=int(eval(input()))
A=int(eval(input()))
if N%500<=A:
    print("Yes")
else:
    print("No")

# Optimized solution
N=int(eval(input()))
A=int(eval(input()))
print(("Yes" if N%500<=A else "No"))
# Original solution
N = eval(input())
A = eval(input())
n = int(N)
a = int(A)


x = n % 500

if x <= a:
	print("Yes")
else:
	print("No")


# Optimized solution
N = int(eval(input()))
A = int(eval(input()))

num = N % 500

if num <= A:
  print("Yes")
else:
  print("No")
# Original solution
if int(eval(input()))%500<=int(eval(input())):
  print("Yes")
else:
  print("No")


# Optimized solution
print((["Yes","No"][int(eval(input()))%500>int(eval(input()))]))
# Original solution
N = int(eval(input()))
A = int(eval(input()))

amari = N % 500

if amari <= A:
    print('Yes')
else:
    print('No')

# Optimized solution
n = int(eval(input()))
a = int(eval(input()))

if n%500 <= a:
  print("Yes")
else:
  print("No")
# Original solution
# https://atcoder.jp/contests/abc088/tasks/abc088_a

n = int(eval(input()))
a = int(eval(input()))
if (n % 500) > a:
    print("No")
else:
    print("Yes")


# Optimized solution
n = int(eval(input()))
a = int(eval(input()))
if n % 500 <= a:
    print("Yes")
else:
    print("No")
# Original solution
N = int(eval(input()))
A = int(eval(input()))

amari = N%500
if amari <= A:
  print('Yes')
else:
  print('No')

# Optimized solution
N = int(eval(input()))
A = int(eval(input()))
print(("Yes" if N%500 <= A else "No"))
# Original solution
print(('No' if max(int(eval(input())) % 500 - int(eval(input())), 0) else 'Yes'))

# Optimized solution
print(('Yes' if int(eval(input())) % 500 <= int(eval(input())) else 'No'))
# Original solution
# -*- coding: utf-8 -*-
N = int(eval(input()))
A = int(eval(input()))
if N % 500 > A:
  print("No")
else:
  print("Yes")

# Optimized solution
N = int(eval(input()))
A = int(eval(input()))
print(("No" if N % 500 != 0 and A <N%500< 500 else "Yes"))
# Original solution
while True:
  n = int(eval(input()))
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  m = int(eval(input()))
  for _ in range(m):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      for y in range(max_v, v - 1, -1):
        dp[y] = max(dp[y], dp[v - 1] + 1)
  print((dp[1000]))


# Optimized solution
while True:
  n = int(eval(input()))
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  m = int(eval(input()))
  for _ in range(m):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      dpv1 = dp[v - 1] + 1
      for y in range(max_v, v - 1, -1):
        if dp[y] < dpv1:
          dp[y] = dpv1
  print((dp[1000]))
# Original solution
while True:
  n = int(eval(input()))
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  m = int(eval(input()))
  for _ in range(m):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      dpv1 = dp[v - 1] + 1
      for y in range(max_v, v - 1, -1):
        if dp[y] < dpv1:
          dp[y] = dpv1
  print((dp[1000]))


# Optimized solution
while True:
  n = int(eval(input()))
  if n == 0:
    break
  hr_lst = []
  for _ in range(n):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  m = int(eval(input()))
  for _ in range(m):
    h, r = list(map(int, input().split()))
    hr_lst.append((h, r))
  
  hr_lst.sort(reverse=True)

  r_lst = [[] for _ in range(1001)]
  for h, r in hr_lst:
    r_lst[h].append(r)
  r_lst = [lst for lst in r_lst if lst != []]
  
  """
  dp[y] ... 最大yまでの最大入れ子数
  dp[y] = max(dp[y], dp[v - 1] + 1)
  """
  dp = [0] * 1001
  for x in range(len(r_lst)):
    vlst = r_lst[x]
    max_v = 1000
    for v in vlst:
      dpv1 = dp[v - 1] + 1
      for y in range(max_v, v - 1, -1):
        if dp[y] < dpv1:
          dp[y] = dpv1
      max_v = v
  print((dp[1000]))
# Original solution
N=int(eval(input()))
L=[]
L=list(map(int,input().split()))
L.sort()
sum=0
for i in range(0,N):
    if(L[i*2]<L[(i*2)+1]):
        sum+=L[i*2]
    else:
        sum+=L[i*2]
print(sum)


# Optimized solution
N=int(eval(input()))
L=[]
L=list(map(int,input().split()))
L.sort()
sum=0
for i in range(0,N):
    sum+=L[i*2]
print(sum)
# Original solution
# coding: utf-8
N = int(eval(input()))
lst = sorted(map(int, input().split()))
print((sum([lst[i] for i in range(2*N) if i %2==0])))

# Optimized solution
# coding: utf-8
N = int(eval(input()))
lst = sorted(map(int, input().split()))
print((sum(lst[::2])))
# Original solution
N = int(eval(input()))
L = list(map(int, input().split(" ")))

L = sorted(L)

tmp= 0
for i in range(N):
    tmp += L[i*2]

print(tmp)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N = int(eval(input()))
    l = sorted(list(map(int, input().split())), reverse=True)

    ans = 0
    for i in range(0, N*2, 2):
        ans += min(l[i], l[i+1])
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
l = sorted(list(li()))
print((sum(l[0::2])))

# Optimized solution
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
l = sorted(list(li()))
print((sum(l[::2])))
# Original solution
n = int(eval(input()))
l = tuple(sorted(map(int, input().split())))

print((sum(l[::2])))

# Optimized solution
eval(input())
print((sum(sorted(map(int, input().split()))[::2])))
# Original solution
eval(input());print((sum(sorted(map(int,input().split()))[::2])))

# Optimized solution
n,l=open(0);print((sum(sorted(map(int,l.split()))[::2])))
# Original solution
N = int(eval(input()))
kushi = sorted(list(map(int,input().split())))
sum = 0
for i in range(2*N):
    if i % 2 == 0:
        sum += kushi[i]
print(sum)


# Optimized solution
N = int(eval(input()))
kushi = sorted(list(map(int,input().split())))
sum = 0
for i in range(0,2*N,2):
    sum += kushi[i]
print(sum)
# Original solution
n = int(eval(input()))
l = list(map(int, input().split()))
l = sorted(l, reverse=True)
t = 0
for i in range(1, n * 2, 2):
    t += min(l[i], l[i-1])
print(t)


# Optimized solution
n = int(eval(input()))
l = sorted(list(map(int, input().split())), reverse=True)
t = 0
for i in range(1, n * 2, 2):
    t += min(l[i], l[i-1])
print(t)
# Original solution
N = int(eval(input()))
src = list(map(int,input().split()))
src.sort()
ans = 0
for a,b in zip(src[::2],src[1::2]):
    ans += a
print(ans)

# Optimized solution
N = int(eval(input()))
L = list(map(int,input().split()))
L.sort(reverse=True)

ans = 0
for a,b in zip(L[::2],L[1::2]):
    ans += min(a,b)
print(ans)
# Original solution
N = int(eval(input()))
L = list(map(int,input().split()))

L = sorted(L)

ans = 0

while len(L) :
    if len(L) == 1 :
        ans += L[0]
        L.pop(0)
    else :
        ans += L.pop(0)
        L.pop(0)

print(ans)


# Optimized solution
N = int(eval(input()))
L = list(map(int,input().split()))

L = sorted(L)

ans = 0
for i in range(0, 2*N, 2) :
    ans += L[i]

print(ans)
# Original solution
"#!/usr/bin/env python3"

N = int(eval(input()))
L = list(map(int,input().split()))

L = sorted(L)

ans = 0
for i in range(0, 2*N, 2) :
    ans += L[i]

print(ans)


# Optimized solution
N = int(eval(input()))
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range(0,2*N,2) :
    ans += L[i]
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=sorted(a)
c=set(a)
count=0
for i in c:
    if b.count(i)==i:
       count+=0
    elif b.count(i)>=i:
       count+=b.count(i)-i
    else:
       count+=b.count(i)
print(count)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=sorted(a)#n
c=list(set(b))
c.sort()
kosuu_list=[]
kosuu=1
for i in range(len(b)-1):
    #kosuu=0
    #print(b[i])
    if b[i]==b[i+1]:
        kosuu+=1
    else:
        kosuu_list.append(kosuu)
        kosuu=1
kosuu_list.append(b.count(b[-1]))
#print(kosuu_list)
count=0
#print(c)
for i in range(len(c)):
    if kosuu_list[i]==c[i]:
        count+=0
    elif kosuu_list[i]>=c[i]:
        count+=kosuu_list[i]-c[i]
    else:
        count+=kosuu_list[i]
print(count)
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))

a.sort()

count = 0

while a:
    k = a.pop(0)
    k_count = 1
    while (len(a) > 0) and (a[0] == k):
        a.pop(0)
        k_count += 1
    if k_count < k:
        count += k_count
    else:
        count += k_count - k
print(count)


# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))

a.sort()

count = 0

while a:
    k = a.pop(-1)
    k_count = 1
    while (len(a) > 0) and (a[-1] == k):
        a.pop(-1)
        k_count += 1
    if k_count < k:
        count += k_count
    else:
        count += k_count - k
print(count)
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))
cnt = 0
S = 0
for i in range(100000):
    tmp = a.count(i + 1)
    S += tmp
    if tmp > i + 1:
        cnt += tmp - i - 1
    elif tmp < i + 1:
        cnt += tmp
cnt += N - S
print(cnt)


# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))
tmp = 1
cnt = 0
S = 0
a.sort()
a.append(0)
for i in range(N):
    if a[i] == a[i + 1]:
        tmp += 1
    else:
        if tmp > a[i]:
            cnt += tmp - a[i]
        elif tmp < a[i]:
            cnt += tmp
        tmp = 1
print(cnt)
# Original solution
N = int(eval(input()))
l = list(map(int, input().split()))
unique_l = list(set(l))
ans = 0
for i in unique_l:
    cnt = l.count(i)
    if cnt==i:
        pass
    elif cnt > i:
        ans += cnt - i
    elif cnt < i:
        ans += cnt
print(ans)

# Optimized solution
N = int(eval(input()))
l = list(map(int, input().split()))
unique_l = list(set(l))
unique_l.sort()
l.sort()
l.append(0)
ans = 0
j = 0
cnt =[]
for i in unique_l:
    temp = 0
    while l[j] == i and j < N:
        temp += 1
        j += 1
    cnt.append(temp)
for i, j in zip(unique_l, cnt):
    if i == j:
        pass
    elif j > i:
        ans += j - i
    elif j < i:
        ans += j
print(ans)
# Original solution
import sys

def main():
	while True:
		m = eval(input())
		if m == 0: return 0
		dp = {}
		dp[(0, 0)] = 1
		for i in range(m):
			v, c = list(map(int, input().split()))
			for j in range(1001):
				for k in range(c + 1):
					key = (i + 1, j + v * k)
					dp.setdefault(key, 0)
					dp[key] += dp.get((i, j), 0)
		n = eval(input())
		for i in range(n):
			x = eval(input())
			print(dp.get((m, x), 0))

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

# Optimized solution
import sys
from array import array

def main():
	while True:
		m = eval(input())
		if m == 0: return 0
		dp = [array('I', [0] * 1001) for i in range(m + 1)]
		dp[0][0] = 1
		for i in range(m):
			v, c = list(map(int, input().split()))
			for j in range(1001):
				for k in range(c + 1):
					next = j + v * k
					if next > 1000: continue
					dp[i + 1][next] += dp[i][j]
		n = eval(input())
		for i in range(n):
			x = eval(input())
			print(dp[m][x])

if __name__ == '__main__':
	sys.exit(main())
# Original solution
while True:
    n = int(eval(input()))
    if n == 0:
        break
    for _ in range(n):
        p = list(map(int, input().split()))
        if 100 in p:
            print("A")
        elif (p[0] + p[1]) // 2 >= 90:
            print("A")
        elif sum(p) // 3 >= 80:
            print("A")
        elif sum(p) // 3 >= 70:
            print("B")
        elif sum(p) // 3 >= 50 and (p[0] >= 80 or p[1] >= 80):
            print("B")
        else:
            print("C")

# Optimized solution
while True:
    n = int(eval(input()))
    if n == 0:
        break
    for _ in range(n):
        p = list(map(int, input().split()))
        x = sum(p) // 3
        if 100 in p:
            print("A")
        elif (p[0] + p[1]) // 2 >= 90:
            print("A")
        elif x >= 80:
            print("A")
        elif x >= 70:
            print("B")
        elif x >= 50 and (p[0] >= 80 or p[1] >= 80):
            print("B")
        else:
            print("C")
# Original solution
import sys

def solve():
    file_input = sys.stdin
    N, K = list(map(int, file_input.readline().split()))
    
    G = [[] for i in range(10)]
    for line in file_input:
        c, g = list(map(int, line.split()))
        G[g - 1].append(c)
    
    for genre in G:
        genre.sort(reverse=True)
        for p, i in zip(genre, list(range(1, len(genre)))):
            genre[i] += p + 2 * i # Recording cumulative price
    
    C = [0] * (K + 1)
    for genre in G:
        pre_C = C.copy()
        for n, p in enumerate(genre, start=1):
            for i, vals in enumerate(zip(pre_C[n:], C)):
                v1, v2 = vals
                v1 += p
                if v1 > v2:
                    C[i] = v1
    print((C[0]))

solve()


# Optimized solution
import sys

def solve():
    file_input = sys.stdin
    N, K = list(map(int, file_input.readline().split()))
    
    G = [[] for i in range(10)]
    for line in file_input:
        c, g = list(map(int, line.split()))
        G[g - 1].append(c)
    
    for genre in G:
        genre.sort(reverse=True)
        for i, p in zip(list(range(1, len(genre))), genre):
            genre[i] += p + 2 * i # Recording cumulative price
    
    C = [0] * (K + 1)
    for genre in G:
        pre_C = C.copy()
        for n, p in zip(list(range(len(genre), 0, -1)), genre[::-1]):
            for i, vals in enumerate(zip(pre_C[n:], C)):
                v1, v2 = vals
                v1 += p
                if v1 > v2:
                    C[i] = v1
    print((C[0]))

solve()