Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      Ar[x for x < A].append[B]
for i in range(M):
      ans += max(Ar[i])
print(ans)
      


### FIXED CODE ###

import heapq
N , M = map(int , input().split())
jobs = [list(map(int , input().split())) for _ in range(N)]
jobs.sort()

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    #print(q)
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

print(ans)
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
from math import sqrt, gcd, factorial, tan, pi, sin, cos
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1]

MOD = 998244353

def solve():
    n = int(input())
    d = [int(x) for x in input().split()]
    f = [0] * n
    for e in d:
        f[e] += 1
    
    ok = f[0] == 1
    z = 0
    ans = 1
    for i in range(1, n):
        if (f[i] == 0): z = 1
        if (z and f[i]): ok = 0
        ans *= pow(f[i-1], f[i], MOD)
        ans %= MOD
    print(ans * ok)




t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()



"""
1 -> (1, 2) -> (2 ** 3, 3) -> (3, 1)

"""



### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# from collections import defaultdict, deque
# from math import sqrt, gcd, factorial, tan, pi, sin, cos
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1]

MOD = 998244353

def solve():
    n = int(input())
    d = [int(x) for x in input().split()]
    f = [0] * n
    for e in d:
        f[e] += 1
    
    ok = f[0] == 1 and d[0] == 0
    z = 0
    ans = 1
    for i in range(1, n):
        if (f[i] == 0): z = 1
        if (z and f[i]): ok = 0
        ans *= pow(f[i-1], f[i], MOD)
        ans %= MOD
    print(ans * ok)




t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()



"""
1 -> (1, 2) -> (2 ** 3, 3) -> (3, 1)

"""
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    dic = {}
    for m in range(1, M + 1):
        dic[m] = 0

    for i in range(N):
        input_raw = read_func().strip().split()
        K = int(input_raw[0])
        for j in range(K):
            dic[int(input_raw[i])] += 1

    count = 0
    for m in dic:
        if dic[m] == N:
            count += 1
    print count


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    dic = {}
    for m in range(1, M + 1):
        dic[m] = 0

    for i in range(N):
        input_raw = read_func().strip().split()
        K = int(input_raw[0])
        for j in range(K):
            dic[int(input_raw[j + 1])] += 1

    count = 0
    for m in dic:
        if dic[m] == N:
            count += 1
    print count


if __name__ == '__main__':
    main()
a,b = map(int(input().split()))
s = -(-b// a)
print(s)

### FIXED CODE ###

a,b = map(int,input().split())
print(-(-(b-1)//(a-1)))
s = input().split()
ss = []
for w in s:
    a = w.find('apple')
    p = w.find('peach')
    if a != -1:
        w = w.replace('apple','peach')
    elif p != -1:
        w = w.replace('peach','apple')
    ss.append(word)
print(' '.join(ss))

### FIXED CODE ###

s = input().split()
ss = []
for w in s:
    a = w.find('apple')
    p = w.find('peach')
    if a != -1:
        w = w.replace('apple','peach')
    elif p != -1:
        w = w.replace('peach','apple')
    ss.append(w)
print(' '.join(ss))
import numpy as np
N = int(input())

A_ls = np.array(list(map(int,input().split(" "))))
B_ls = np.array(list(map(int,input().split(" "))))

S = 0

for i,a in A_ls:
    if a > B_ls[i]:
        B_ls[i] == 0
        a -= B_ls[i]
        S += B_ls[i]
        if B_ls[i+1] >= a:
            B_ls[i+1] -=a
            S+=a
        elif:
            B_ls[i+1] = 0
            S+=(B_ls[i+1])
    elif:
        S += a

print(S)


### FIXED CODE ###


import numpy as np
N = int(input())

A_ls = np.array(list(map(int,input().split(" "))))
B_ls = np.array(list(map(int,input().split(" "))))

S = 0

for i,b in enumerate(B_ls):
    if b > A_ls[i]:
        b -= A_ls[i]
        S += A_ls[i]
        if A_ls[i+1] >= b:
            A_ls[i+1] -=b
            S+=b
        else:
            S+=A_ls[i+1]
            A_ls[i+1] = 0 
    else:
        S += b

print(S)
H,N=map(int,input().split())
A=[]
for i in range(N):
  A.append(int(input()))
print('YNeos'[H<sum(A)::2])
           

### FIXED CODE ###

H,N=map(int,input().split())
print('NYoe s'[H<=sum(list(map(int,input().split())))::2])
N, K = map(int, input().split())
 
tmp = [0] * N
 
for i in range(K):
  input()
  for j in map(int, input().split()):
 	tmp[j-1] |= 1 
print(sum(tmp))

### FIXED CODE ###

N, K = map(int, input().split())
 
tmp = set()
 
for i in range(K):
  input()
  tmp |= set(map(int, input().split()))
 
print(len(set(range(1, N+1)) - tmp))
a = list(map(int,input().split()))

for i in range(a[0,a[1]+1]):
    if i % a[2] == 0:
        counter += 1
print(counter)

### FIXED CODE ###

a = list(map(int,input().split()))
counter = 0

for i in range(a[0],a[1]+1):
    if i % a[2] == 0:
        counter += 1
print(counter)
import sympy
#sympy.divisors(10**9)
n = int(input())

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

a.sort(reverse = True)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

if len(set(a)) == 1:
    print(0)
else:
    
    
    ans = 0

    for i in range(n):
        target = make_divisors(a[i])
        if len(set(target) & set(a)) == 1:
            ans += 1

    print(ans)
        

### FIXED CODE ###

n = int(input())

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

M = 1000005

cnt = [0 for i in range(M)]

for x in a:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x, M, x):
        cnt[i] += 1

ans = 0

for x in a:
    if cnt[x] == 1:
        ans += 1
    
print(ans)
n1 = input()
n = list(n1)
ans = 0
for i in n:
  ans += 1
if n%ans ==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
n_=[int(i) for i in str(n)]
s=sum(n_)
if n%s==0:
    print('Yes')
else:
    print('No')
import math
from functools import reduce

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

## 最初に入力回数が与えられて、そのあとデータが入力される。といったパターン
nums = list(map(int, input().split())) # "1 2 3"と入力
N = nums[0]
X = nums[1]

nums = list(map(int, input().split())) # "1 2 3"と入力

a=[]
for item in nums:
	a.append(abs(item - X))


print(gcd (*a))


### FIXED CODE ###

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

x = list(map(lambda x: abs(x - X), x))


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

ans = x[0]
for i in x:
    ans = min(ans, gcd(i, ans))
print(ans)
n, a, b = map(int, input().split())A
print((b - a) * (n - 2) + 1)


### FIXED CODE ###

n, a, b = map(int, input().split())
x = a * n - a + b
y = b * n - b + a


if a > b:
    print(0)
elif a == b and n == 1:
    print(1)
elif a != b and n == 1:
    print(0)
else:
    print(y - x + 1)
import sys
import collections
from functools import lru_cache

sys.setrecursionlimit(10 ** 5 + 1)
xy = []
d = collections.defaultdict(list)

@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import collections
from functools import lru_cache

xy = []
d = collections.defaultdict(list)
@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    sys.setrecursionlimit(10 ** 5 + 1)
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()
n,m = input().split()n,m = input().split()
n = int(n)
m = int(m)
arr = list(map(int,input().split()))
minn = sum(arr)*(1/(4*m))
t = 0
for i in arr:
  if i >= minn:
    t += 1
if t >= m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m = input().split()
n = int(n)
m = int(m)
arr = list(map(int,input().split()))
minn = sum(arr)*(1/(4*m))
t = 0
for i in arr:
  if i >= minn:
    t += 1
#print(t)
if t >= m:
  print("Yes")
else:
  print("No")
s = input('enter a number')
w = input('enter a number')
print('safe' if s > w else 'unsafe')

### FIXED CODE ###

num = map(int,input().split())
a = []
for i in num:
    a.append(i)
if a[0]<a[1]:
    print('unsafe')
elif a[0]>a[1]:
    print('safe')
else:
    print('unsafe')
s = list(input())
t = list(input())
s = s.sort()
t = t.sort()
t = t.reverse()

s = ''.join(s)
t = ''.join(t)
if s < t :
  print('Yes')
else :
  print('No')

### FIXED CODE ###

s = list(input())
t = list(input())
s.sort()
t.sort()
t.reverse()
s = ''.join(s)
t = ''.join(t)
if s < t:
  print('Yes')
else:
  print('No')
#encoding utf-8

n = int(input())
v = list(int(i) for i in input().split())


v_odd = []
v_even = []
for i in range(n):
    if i%2 == 0:
        v_odd.append(v[i])
    else:
        v_even.append(v[i])

#odd part
count={}
for i in range(len(v_odd)):
    if v_odd[i] in count.keys():
        count[v_odd[i]] += 1
    else:
        count[v_odd[i]] = 1



for k, v in sorted(count.items(), key=lambda x: -x[1]):
    pass
keys = list(count.keys())
# num_odd = len(v_odd)-int(count[keys[0]])


#even part
even_count={}

for i in range(len(v_even)):
    if v_even[i] in even_count.keys():
        even_count[v_even[i]] += 1
    else:
        even_count[v_even[i]] = 1


for k, v in sorted(even_count.items(), key=lambda x: -x[1]):
    pass
even_keys = list(even_count.keys())
# num += len(v_even)-int(count[even_keys[0]])


if even_keys[0] == keys[0]:
    if len(keys) == 1 and len(even_keys) == 1:
        answer = int(n/2)
    elif len(keys) == 1:
        answer = int(n/2)-int(even_count[even_keys[1]])
    elif len(even_keys) == 1:
        answer = int(n/2)-int(count[keys[1]])
    else:
        if int(v_even[even_keys[0]]) >= int(v_odd[keys[0]]):
            answer = n-int(count[keys[1]])-int(even_count[even_keys[0]])
        else:
            answer = n-int(count[keys[0]])-int(even_count[even_keys[1]])
else:
    answer = n-int(count[keys[0]])-int(even_count[even_keys[0]])
print(int(answer))


### FIXED CODE ###

from collections import Counter
def main(n,v):
    # n = int(input())
    # v = list(map(int, input().split()))
    odd = Counter(v[0::2]).most_common(2) + [(0, 0)]
    even = Counter(v[1::2]).most_common(2) + [(0, 0)]

    n_half = int(n / 2)

    if (len(odd) == 1 and len(even) == 1) and odd[0][0] == even[0][0]:
        ans = n_half
    elif odd[0][0] == even[0][0]:
        ans = min(n_half - odd[0][1] + n_half - even[1][1],\
                n_half - odd[1][1] + n_half - even[0][1])
    else:
        ans = n_half - odd[0][1] + n_half - even[0][1]

    print(ans)
    return 0

if __name__ == "__main__":
    n = int(input())
    v = list(map(int, input().split()))
    main(n,v)
s = input()
if s = 'SUN':
  print(7)
elif s = 'SAT':
  print(1)
elif s = 'MON':
  print(6)
elif s = 'TUE':
  print(5)
elif s=  'WED':
  print(4)
elif s = 'THU':
  print(3)
elif s = 'FRI':
  print(2)

### FIXED CODE ###

s = input()
if s == 'SUN':
  print(7)
elif s == 'SAT':
  print(1)
elif s == 'MON':
  print(6)
elif s == 'TUE':
  print(5)
elif s==  'WED':
  print(4)
elif s == 'THU':
  print(3)
else:
  print(2)
from itertools import permutations
import numpy as np
N=int(input())
l=[i+1 for i in range(N)]
P=np.array(list(map(int, input().split())))
Q=np.array(list(map(int, input().split())))
counter=0
for t in permutations(l):
  tmp=np.array(t)
  if all(P==tmp):
    a=counter
    
  if all(Q==tmp):
    b=counter
    
  counter+=1
  
print(abs(a-b))

### FIXED CODE ###

from itertools import permutations

N=int(input())
l=[i+1 for i in range(N)]
P=tuple(map(int, input().split()))
Q=tuple(map(int, input().split()))
counter=0
for t in permutations(l):
  if P==t:
    a=counter
    
  if Q==t:
    b=counter
    
  counter+=1
  
print(abs(a-b))
X = int(input())

num_list = [0]*100001
num_list[0] = 1

for i in range(100001 + 1 + 105):
    if i == X:
        print(num_list[X])
        exit()

    for j in [100, 101, 102, 103, 104, 105]:
        if num_list[i]:
            num_list[i+j] = 1

print(0)

### FIXED CODE ###

X = int(input())

num_list = [0]*(100001 + 105)
num_list[0] = 1

for i in range(100001 + 105):
    if i == X:
        print(num_list[X])
        exit()

    for j in [100, 101, 102, 103, 104, 105]:
        if num_list[i]:
            num_list[i+j] = 1

print(0)
# メモ化再帰
import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

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

N = int(input())
h = inpl()

INF = float('inf')

# 最小化問題なのでINFに初期化
dp = [ INF for _ in range(100010) ]

def solve(i):
    # DPの値が更新されていたらそのまま
    if dp[i] < INF:
        return dp[i]

    # 足場0のコストは0
    if i == 0:
        return 0

    # dp[i]の計算
    res = float("inf")
    ## 足場i-1から来た場合
    res = min(res, solve(i-1) + abs(h[i] - h[i-1]))
    ## 足場i-2から来た場合
    if i > 1:
        res = min(res, solve(i-2) + abs(h[i] - h[i-2]))

    # メモ
    dp[i] = res

    return res


print(solve(N-1))

### FIXED CODE ###

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

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

N = int(input())
h = inpl()

INF = 10e11

# 最小化問題なのでINFに初期化
dp = [ INF for _ in range(100010) ]

# 初期状態
dp[0] = 0

# ループ
for i in range(1, N):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])
n=int(input())

result=[]
for i in range(1,n+1):
    if i %3==0:
        result.append(i)
    else:
        k=i
        for j in range(1,len(str(n)+1):
            if k%(10**j)==3:
                result.append(i)
                break
            else:
                k=k//10**j
        else:
            continue

print(*result

### FIXED CODE ###

n=int(input())
 
result=[]
for i in range(1,n+1):
    if i %3==0:
        result.append(i)
    else:
        k=i
        for j in range(1,5):
            if k%10==3:
                result.append(i)
                break
            else:
                k=k//10
        else:
            continue
 
print("",*result)
a=int(input())
for x in range(int(a**0.5),0,-1)
	if a%x==0:
    d==a//x
    s==d+x-2
    break
print(s)

### FIXED CODE ###

a=int(input())
for x in range(int(a**0.5),0,-1):
  if a%x==0:
    b=int(a//x)
    break
print(b+x-2)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

s = [tuple(map(int, input().split())) for _ in range(N)]
s.sort(key = lambda x: -x[1])
table = [(-1, -1)] * (N + 1)
c = 0
for i in range(N):
  if table[s[i][0]] == (-1, -1):
    table[s[i][0]] = (i, s[i][1])
    c += 1

table.sort(key = lambda x: -x[1])
res = [0] * (M + 1)
vis = set()
p = M
for i in range(M): res[0] += s[i][1]
for x in range(1, c + 1):
  res[x] = res[x - 1] + pow(x, 2) - pow(x - 1, 2)
  if table[x - 1][0] >= M:
    res[x] += table[x - 1][1]
    p -= 1
    while p in vis:
      p -= 1
    res[x] -= s[p][1]
  vis.add(table[x - 1][0])
  #print(p)
print(max(res))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

s = [tuple(map(int, input().split())) for _ in range(N)]
s.sort(key = lambda x: -x[1])
table = [(-1, -1)] * (N + 1)
c = 0
for i in range(N):
  if table[s[i][0]] == (-1, -1):
    table[s[i][0]] = (i, s[i][1])
    c += 1

table.sort(key = lambda x: -x[1])
res = [0] * (min(c, M) + 1)
vis = set()
p = M
for i in range(M): res[0] += s[i][1]
for x in range(1, min(c, M) + 1):
  res[x] = res[x - 1] + pow(x, 2) - pow(x - 1, 2)
  if table[x - 1][0] >= M:
    res[x] += table[x - 1][1]
    p -= 1
    while p in vis:
      p -= 1
    res[x] -= s[p][1]
  vis.add(table[x - 1][0])
  #print(p)
print(max(res))
import functools
import math
def slcm(numbers):
	return functools.reduce(lambda x,y:x*y//math.gcd(x,y),numbers)

input()
numbers=list(map(int,input().split()))
num=slcm(numbers)-1
print(sum([num%i for i in numbers]))

### FIXED CODE ###

import functools
import fractions

def blcm(x, y):
	return (x*y)//fractions.gcd(x, y)

def slcm(numbers):
	return functools.reduce(blcm, numbers)
	
input()
numbers=list(map(int, input().split()))
num=slcm(numbers)-1
nums=[num%i for i in numbers]
print(sum(nums))
print(r*r)

### FIXED CODE ###

r = int(input())
print(r*r)
a = input()
b = input()
if a = b[:-1]:
  print("yes")
else:
  print("No")

### FIXED CODE ###

a,b = [input() for i in range(2)]
 
if a == b[:-1]:
  print("Yes")
else:
  print("No")
n = int(input())
home_list = input().split()
home_list.sort()
print(hpme_list[n-1] - home_list[0])

### FIXED CODE ###

n = int(input())
home_list = list(map(int, input().split()))
home_list.sort()
print(home_list[n-1] - home_list[0])
from collections import deque
n, m = map(int, input().split())
dir = [[] for _ in range(m+1)]

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [False]*(n+1)
flag[1] = True
que = deque([1])
while que:
    #print('que: ', len(que), que)
    now = que.popleft()
    for to in dir[now]:
        if flag[to]:
            continue
        que.append(to)
        flag[to] = True
        ans[to] = now
"""         print(to)
        ans[to] = now
        flag[to] = 1
        for toto in dir[to]:
            if flag[toto] != 1:
                que.append(toto) """
print('Yes')
for i in range(2,n+1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
dir = [[] for _ in range(n+1)]

for i in range(m):
    ta, tb = map(int, input().split())
    dir[ta].append(tb)
    dir[tb].append(ta)

ans = [0]*(n+1)
flag = [False]*(n+1)
flag[1] = True
que = deque([1])
while que:
    #print('que: ', len(que), que)
    now = que.popleft()
    for to in dir[now]:
        if flag[to]:
            continue
        que.append(to)
        flag[to] = True
        ans[to] = now

print('Yes')
for i in range(2,n+1):
    print(ans[i])
s = input()
t = input()
n = len(s)
if s = t[:n]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
t = input()
n = len(s)
if s == t[:n]:
  print("Yes")
else:
  print("No")
import sys
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
a = input()
a = int(a)
if  a == 1:
 print("Yes")
 sys.exit()
 else:
  k = range(1,a)
  for s in k:
   res = a/s
   #print("s",s)
   #print("res",res)
   try:
    res = int(res)
   except:
    break
   if is_integer(s):
    if is_integer(res):
     if len(str(s)) == 1:
      if len(str(res)) == 1:
       #print(res,s)
       if res * s == a:
        print("Yes")
        sys.exit() 
print("No")

### FIXED CODE ###

import sys
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
a = input()
a = int(a)
if  a == 1:
 print("Yes")
 sys.exit()
k = range(1,a)
for s in k:
 res = a/s
 #print("s",s)
 #print("res",res)
 try:
  res = int(res)
 except:
  break
 if is_integer(s):
  if is_integer(res):
   if len(str(s)) == 1:
    if len(str(res)) == 1:
     #print(res,s)
     if res * s == a:
      print("Yes")
      sys.exit() 
print("No")
n = int(input())
book=[]
for i in range(n):
    a,b=input().split()
    temp=[a,int(b),i+1]
    book.append(temp)

book.sort(key = lambda x:x[1], reverce = True)
book.sort(key = lambda x:x[0])

for j in range(len(book)):
    print(book[j][2])

### FIXED CODE ###

n = int(input())
l = [input().split()+[i+1] for i in range(n)]
for i in range(n):
    l[i][1] = int(l[i][1])
l = sorted(l, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[0])
for i in range(n):
    print(l[i][2])
from math import factorial

def comb(n, r):
    if n == 1:
        return 0
    return factorial(n) / factorial(r) / factorial(n - r)

N = int(input())
S = [input() for _ in range(N)]
str_dict = {}
for s in S:
    sorted_s = "".join(sorted(s))
    if sorted_s not in str_dict:
        str_dict[sorted_s] = 0
    str_dict[sorted_s] += 1
ans = sum([comb(v, 2) for v in str_dict.values()])
print(int(ans))

### FIXED CODE ###

from math import factorial

def comb(n, r):
    if n == 1:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

N = int(input())
S = [input() for _ in range(N)]
str_dict = {}
for s in S:
    sorted_s = "".join(sorted(s))
    if sorted_s not in str_dict:
        str_dict[sorted_s] = 0
    str_dict[sorted_s] += 1
ans = sum([comb(v, 2) for v in str_dict.values()])
print(int(ans))
case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    msg = "Case "+str(case)+":"
    print(msg)
    print('\n'.join(map(str,bestVW(N-1,W))))




### FIXED CODE ###

nCase = 0
while True:
    W = int(input())
    if W == 0: break
    nCase += 1
    N = int(input())
    # [(value, weight), ... ]
    items = [tuple(map(int, input().split(','))) for _ in range(N)]
    bestValueFor = [0] * (W + 1) # item -> best value, idx -> capacity 
    for item in items:
        for capa in reversed(range(W-item[1]+1)):
            # if taken wins not taken
            if bestValueFor[capa] + item[0] > bestValueFor[capa + item[1]]:
                bestValueFor[capa + item[1]] = bestValueFor[capa] + item[0]
    bestValue = max(bestValueFor)
    bestWeight = bestValueFor.index(bestValue)
    print('Case ',str(nCase),':',sep='')
    print(bestValue)
    print(bestWeight)