Harryxun/stf_run huggingface dataset:
# D - Summer Vacation

_input = list(map(int, input().split()))
n = _input[0]
m = _input[1]
jobs = dict()
for i in range(n):
    __input = list(map(int, input().split()))
    a = __input[0]
    b = __input[1]
    item = jobs[b] if b in jobs else list()
    item.append(a)
    item.sort(reverse=True)
    jobs[b] = item

sorted(jobs.items(), key=lambda j: -j[0])
reward = 0
while m > 0:
    for b, aList in jobs:
        if len(aList) > 0 and m >= aList[0]:
            reward += b
            aList.pop(0)
            jobs[b] = aList
            break
    m -= 1

print(reward)

### FIXED CODE ###

# D - Summer Vacation ★
from collections import defaultdict
from heapq import heappush, heappop

_input = list(map(int, input().split()))
n = _input[0]
m = _input[1]
jobs = defaultdict(list)

# かかる日数ごとに報酬をまとめる
for i in range(n):
    a, b = list(map(int, input().split()))
    if a <= m:
        jobs[a].append(b)

# M-1日目、M-2日目…と後ろから順に得られる報酬が多い仕事を割り振っていく
# ※日数制限があったほうが埋めやすいので
reward = 0
heapsort = []
for daysLeft in range(1, m + 1):
    if daysLeft in jobs:
        for b in jobs[daysLeft]:
            heappush(heapsort, -b)
    if len(heapsort) > 0:
        reward += -heappop(heapsort)
print(reward)
s = input()
n = int(input())
for i in range(n):
    order, a, b, *c = input().split()
    a = int(a)
    b = int(b)
    if order == 'replace':
        s = s[:a] + c[0] + s[b+1:]
    elif order[0] == 'r':
        s = s[:a] + s[::-1][len(s)-b-1:len(s)-a]+ s[b+1:]
    else:
        print(s[a:b+1])


### FIXED CODE ###

while 1:
    a = input()
    if a == '-':
        break
    n = int(input())
    for i in range(n):
        h = int(input())
        a = a[h:] + a[:h]
    print(a)
import itertools

def main():
    N, M = map(int, input().split())
    VE = tuple(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))
    # print(VE)

    adj_mat = [[0 for _ in range(N)] for _ in range(M)]
    for ve in VE:
        adj_mat[ve[0]][ve[1]] = 1
        adj_mat[ve[1]][ve[0]] = 1
    # for row in adj_mat:
    #     print(row)

    ans = 0
    for perm in itertools.permutations([i for i in range(1, N)]):
        # print(perm)
        flag = True
        now_V = 0
        for next_V in perm:
            # print('{} to {}'.format(now_V, next_V))
            # print('{}'.format(adj_mat[now_V][next_V]))
            if not adj_mat[now_V][next_V]:
                flag = False
                break
            now_V = next_V
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools

def main():
    N, M = map(int, input().split())
    VE = tuple(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))
    # print(VE)

    adj_mat = [[0 for _ in range(N)] for _ in range(N)]
    for ve in VE:
        adj_mat[ve[0]][ve[1]] = 1
        adj_mat[ve[1]][ve[0]] = 1
    # for row in adj_mat:
    #     print(row)

    ans = 0
    for perm in itertools.permutations([i for i in range(1, N)]):
        # print(perm)
        flag = True
        now_V = 0
        for next_V in perm:
            # print('{} to {}'.format(now_V, next_V))
            # print('{}'.format(adj_mat[now_V][next_V]))
            if not adj_mat[now_V][next_V]:
                flag = False
                break
            now_V = next_V
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()
n = input()
digit = n % 10
if(digit == 3)
  print ("bon")
elif(digit == 0 and digit == 1 and digit == 6 and digit == 8)
  print ("pon")
else:
  print ("hon")


### FIXED CODE ###

ninput = input() #これはstr型
n = int(ninput) #これでint型に直す
digit = n % 10
if digit == 3:
  print('bon')
elif digit == 0 or digit == 1 or digit == 6 or digit == 8:
  print('pon')
else:
  print('hon')
import sys
a,b=map(int,input().split())
for i in range(1,1100):#max_a=1
    if int(i*0.08)==a and int(i*0.1)==b:
        ans=i
        break
    if i==1099:
        ans=-1

print(ans)


### FIXED CODE ###

a=list(input())
if a[0]==a[1]==a[2]:
  print("No")
else:
  print("Yes")
from sys import setrecursionlimit as srl; srl(10**7)
rr = lambda: int(raw_input())
rrm = lambda: map(raw_input().split())

YES,NO = "APPROVED","DENIED"
def solve(N, A):
    for x in A:
        if x % 2 == 0:
            if x % 3 or x % 5:
                return NO
    return YES

    
print solve(int(rr()), rrm())


### FIXED CODE ###

from sys import setrecursionlimit as srl; srl(10**7)
rr = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

YES,NO = "APPROVED","DENIED"
def solve(N, A):
    for x in A:
        if x % 2 == 0:
            if x % 3 and x % 5:
                return NO
    return YES

    
print solve(int(rr()), rrm())
M, K = map(int, input().split())

if K>=(2**M):
    print(-1)
elif M==0:
    if K==0:
        print(0, 0)
    else:
        print(-1)
elif M==1:
    if K==0:
        print(0, 0, 1, 1)
    else:
        print(0)
else:
    b = [i for i in range(2**M)]
    c = reversed([i for i in range(2**M)])
    print(' '.join(b+[K]+c+[K]))

### FIXED CODE ###

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

if K>=(2**M):
    print(-1)
elif M==0:
    if K==0:
        print(0, 0)
    else:
        print(-1)
elif M==1:
    if K==0:
        print(0, 0, 1, 1)
    else:
        print(-1)
else:
    b = [str(i) for i in range(2**M) if not i==K]
    c = [str(i) for i in range(2**M-1, -1, -1) if not i==K]
    ans = b+[str(K)]+c+[str(K)]
    print(' '.join(ans))
S = list(input())

s_1 = int(S[0:1])
s_2 = int(S[2:])

YYMM = False
MMYY = False

if 1<=s_2<=12:
    YYMM = True
if 1<=s_1<=12:
    MMYY = True
    
if YYMM and MMYY:
    print('AMBIGUOUS')
elif YYMM:
    print('YYMM')
elif MMYY:
    print('MMYY')
else:
    print('NA')

### FIXED CODE ###

S = input()

s_1 = int(S[0:2])
s_2 = int(S[2:])

YYMM = False
MMYY = False

if 1<=s_2<=12:
    YYMM = True
if 1<=s_1<=12:
    MMYY = True
    
if YYMM and MMYY:
    print('AMBIGUOUS')
elif YYMM:
    print('YYMM')
elif MMYY:
    print('MMYY')
else:
    print('NA')
# -*- coding: utf-8 -*-
INF = 10000
n = int(input())
h = list(map(int, input().split()))
dp = [INF]*n

def chmin(a, b):
    if a > b:
        return b
    else:
        return a


def chmax(a, b):
    if a < b:
        return b
    else:
        return a


def rec(i):
    if dp[i] < INF:
        return dp[i]
    if i == 0:
        return 0
    res = INF
    res = chmin(res, rec(i-1) + abs(h[i] - h[i-1]))
    if i > 1:
        res = chmin(res, rec(i - 2) + abs(h[i] - h[i - 2]))
    dp[i] = res
    return dp[i]

print(rec(n-1))


### FIXED CODE ###

# -*- coding: utf-8 -*-
INF = 1000000000
n = int(input())
h = list(map(int, input().split()))
dp = [INF]*n
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])
import re
s=input()

def hoge(str):
	if(str == ""):
		return "YES"
	if(str.startswith("maerd")):
		return hoge(re.sub('^maerd', '', str))
	if(str.startswith("remaerd")):
		return hoge(re.sub('^remaerd', '', str))
	if(str.startswith("esare")):
		return hoge(re.sub('^esare', '', str))
	if(str.startswith("resare")):
		return hoge(re.sub('^resare', '', str))
	return "NO"

print(hoge(s[::-1]))

### FIXED CODE ###

def main():
    S = input()

    while len(S) >= 5:
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

main()
N, K = map(int, input().split())

if N % 2:
  print(int(N / K))
else:
  even = int(N / K)
  odd = int(N / int(K / 2)) - even
  print(pow(even, 2) + pow(odd, 2))

### FIXED CODE ###

N, K = map(int, input().split())
 
if K % 2 == 1:
  print(pow(int(N / K), 3))
else:
  even = int(N / K)
  odd = int(N / int(K / 2)) - even
  print(pow(even, 3) + pow(odd, 3))
n=int(input())

a=[]
for i in range(1,201,2):
    s=0
    for j in range(1,int(i**0.5)+1):
        if i%j==0:
            s+=1
            if j != i//j:
                s+=1
    a.append(s)

ans=0
for i in range(n//2+1):
    if a[i]==8:
        ans+=1

print(ans)

### FIXED CODE ###

n=int(input())

a=[]
for i in range(1,201):
    s=0
    for j in range(1,int(i**0.5)+1):
        if i%j==0:
            s+=1
            if j != i//j:
                s+=1
    a.append(s)

ans=0
for i in range(n):
    if a[i]==8 and i%2==0:
        ans+=1

print(ans)
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t

stack=sorted(kyori[-2])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)

visited=set([len(XYR)-1])
#print(Pdic)
#print(dic)
#print(stack)
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            #if Pdic[i]>nm:
            #    Pdic[i]=nm
            heappush(stack,nm)
            if not nm in dic:
                #kyoriset.add(nm)
                dic.update({nm:[i]})
            else:
                dic[nm].append(i)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t
stack=sorted(kyori[-1])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)
A = list(map(int,input().split))
B = (A[0]+A[1])/2
if B >= int(B):
  print(int(B)+1)
else:
  print(int(B))

### FIXED CODE ###

A = list(map(int,input().split()))
B = (A[0]+A[1])/2
if B > int(B):
  print(int(B)+1)
else:
  print(int(B))
n = int(input())

al = [int(i) for i in input().split()]
bl = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    if bl[i] <= al[i]:
        ans += bl[i]
    elif bl[i] > al[i] and bl[i] <= al[i] + al[i+1]:
        ans += bl[i]
        al[i+1] = al[i] + al[i+i] - bl[i]
    else:
        ans += al[i] + al[i+1]
        al[i+1] == 0
        
print(ans)
        

### FIXED CODE ###

n = int(input())
al = [int(i) for i in input().split()]
bl = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    if al[i] > bl[i]:
        ans += bl[i]
    elif al[i] + al[i+1] > bl[i]:
        ans += bl[i]
        al[i+1] = al[i+1] + al[i] - bl[i]
    else:
        ans += al[i] + al[i+1]
        al[i+1] = 0
        
print(ans)
N=int(input())
H=list(map(int,input().split()))
count=0
ans=[]
for i in range(1,N):
    if H[i-1]>=H[i]:
        count+=1
        if i==N-1:
            ans.append(count)
    else:
        ans.append(count)
        count=0
print(max(ans))

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
count=0
ans=[]
for i in range(1,N):
    if H[i-1]>=H[i]:
        count+=1
        if i==N-1:
            ans.append(count)
    else:
        ans.append(count)
        count=0

if N==1:
    print(0)
else:
    print(max(ans))
name_a,name_b=(x for x in input().split())
a_count,b_count=(int(x) for x in input().split())
fetch_color=input()
 
if fetch_color==name_a:
  a_coount = a_count-1
elif:
  fetch_color==name_b
  b_count = b_count-1
print(a_count,b_count)

### FIXED CODE ###

a,b=input().split()
a_num,b_num=input().split()
c=input()
 
if c==a:
  a_num=int(a_num)-1
elif c==b:
  b_num=int(b_num)-1
print(a_num,b_num)
s = list(input().split("T"))
x, y = map(int, input().split())
s2 = [len(x) for x in s]
pos = [0, 0]
LR = [s2[i] for i in range(len(s2)) if i % 2 == 0]
UD = [s2[i] for i in range(len(s2)) if i % 2 == 1]


flag = False
tmp = 1
tmp = tmp << sum(LR)
for d in LR:
    tmp = tmp << d | tmp >> d

if x >= 0:
    tmp = tmp >> sum(LR)
    if (tmp >> x) % 2 == 1:
        flag = True
else:
    if (tmp >> (sum(LR) + x)) % 2 == 1:
        flag = True
if flag:
    tmp = 1
    tmp = tmp << sum(UD)
    for d in UD:
        tmp = tmp << d | tmp >> d
    if y >= 0:
        tmp = tmp >> sum(UD)
        if (tmp >> y) % 2 == 1:
            flag = True
    else:
        if tmp >> (sum(UD) + y) % 2 == 1:
            flag = True

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


### FIXED CODE ###

s = list(input().split("T"))
x, y = map(int, input().split())
s2 = [len(x) for x in s]
LR = [s2[i] for i in range(len(s2)) if i % 2 == 0]
UD = [s2[i] for i in range(len(s2)) if i % 2 == 1]

flag = False
tmp = 1
tmp = tmp << sum(LR)
for i, d in enumerate(LR):
    if i != 0:
        tmp = tmp << d | tmp >> d
    else:
        tmp = tmp << d

if x >= 0:
    tmp = tmp >> sum(LR)
    if (tmp >> x) % 2 == 1:
        flag = True
else:
    if sum(LR) + x >= 0:
        if (tmp >> (sum(LR) + x)) % 2 == 1:
            flag = True
if flag:

    tmp = 1
    tmp = tmp << sum(UD)
    flag = False
    for d in UD:
        tmp = tmp << d | tmp >> d
    if y >= 0:
        tmp = tmp >> sum(UD)
        if (tmp >> y) % 2 == 1:
            flag = True
    else:
        if sum(UD) + y >= 0:
            if (tmp >> (sum(UD) + y)) % 2 == 1:
                flag = True

if flag:
    print("Yes")
else:
    print("No")
a, v = map(int,input().split())
b, w = map(int,input().split())
t =int(input())

s = abs(b-a)
y = (v-w)

if y <= 0:
    print('NO')
else:
    m = s % y
    u = s //y
    if m == 0 and u <= t
            print('YES')
    else:
        print('NO') 

### FIXED CODE ###

a, v = map(int,input().split())
b, w = map(int,input().split())
t =int(input())

s = abs(b-a)
y = (v-w)

if y <= 0:
    print('NO')
else:
    m = s % y
    u = s //y
    if m == 0 and u <= t:
            print('YES')
    elif m != 0 and u + 1 <= t:
            print('YES')
    else:
        print('NO')
a=input()
total=0
while i < a:
  if i %5 != 0 and i %3 != 0:
    total += a

print(total)

### FIXED CODE ###

a = int(input())
total = 0
for i in range(1, a+1):
  if i % 5 != 0 and i % 3 != 0:
    total += i

print(total)
from collections import deque
w,h = list(map(int,input().split(" ")))
path = [input() for _ in range(w)]

def bfs(sw,sh):
    res = 0
    dw = [-1,1,0,0]
    dh = [0,0,1,-1]
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[sw][sh] = 0
    queue = deque()
    queue.append((sw,sh))
    while len(queue) != 0:
        cw,ch = queue.popleft()
        for i in range(4):
            nw,nh = cw + dw[i], ch + dh[i]
            if not (0<= nw < w and 0 <= nh < h): continue
            if path[nw][nh] == "#": continue
            if dist[nw][nh] != -1: continue
            dist[nw][nh] = dist[cw][ch] + 1
            queue.append((nw,nh))
            res = max(res, dist[nw][nh])
    return res

ans = 0
for i in range(w):
    for j in range(h):
        if path[i][j] == "#":
            continue
        ans = max(ans, bfs(i,j))
print(ans)

### FIXED CODE ###

from collections import deque
w,h = list(map(int,input().split(" ")))
path = [input() for _ in range(w)]

def bfs(sw,sh):
    res = 0
    dw = [-1,1,0,0]
    dh = [0,0,1,-1]
    dist = [[-1 for _ in range(h)] for _ in range(w)]
    dist[sw][sh] = 0
    queue = deque()
    queue.append((sw,sh))
    while len(queue) != 0:
        cw,ch = queue.popleft()
        for i in range(4):
            nw,nh = cw + dw[i], ch + dh[i]
            if not (0<= nw < w and 0 <= nh < h): continue
            if path[nw][nh] == "#": continue
            if dist[nw][nh] != -1: continue
            dist[nw][nh] = dist[cw][ch] + 1
            queue.append((nw,nh))
            res = max(res, dist[nw][nh])
    return res

ans = 0
for i in range(w):
    for j in range(h):
        if path[i][j] == "#":
            continue
        ans = max(ans, bfs(i,j))
print(ans)
n,r = map(int,input().split())
if n>=10:
    print(r)
else:
    print(100*(10-k))
    

### FIXED CODE ###

n,r = map(int,input().split())
if n>=10:
    print(r)
else:
    print(r+100*(10-n))
import numpy as np
N = int(input())
Hs = np.array(list(map(int, input().split())), dtype='int64').reshape(-1, 1)
As = Hs.repeat(N, axis=1)
h = As.T.copy()
L = np.array([i for i in range(N)], dtype='int64').reshape(-1, 1)
idxs = L.repeat(N, axis=1)
tidxs = idxs.T.copy()
co = As + h - np.abs(idxs-tidxs)
ans = N**2-np.count_nonzero(co)
print(ans//2)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
L = [A[i]+i for i in range(N)]
R = [i-A[i] for i in range(N)]
c = Counter(R)

ans = 0
for l in L:
    ans += c[l]

print(ans)
n,*s=open(0);for t in['AC','WA','TLE','RE']:print(t,'x',s.count(t+'\n'))

### FIXED CODE ###

n,*s=open(0).read().split()
for t in['AC','WA','TLE','RE']:print(f'{t} x {s.count(t)}')
import sys
input = sys.stdin.readline

N = int(input())
A = [None]*N
B = [None]*N
K = 0

adj_list=[[] for _ in range(N)]
c_mat = [[-1]*N for _ in range(N)]
c_min_list=[-1]*N #A[i]に隣接する中で使っている色の最小値をメモ

for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    adj_list[A[i]-1].append(B[i]-1)
    adj_list[B[i]-1].append(A[i]-1)
    
#着色
def dfs(node_num,p_num,p_col):
    for i in range(len(adj_list[node_num])):
        to=adj_list[node_num][i]
        #親以外につながる辺を塗る
        if to!=p_num:
            #色を決める
            c_to = c_min_list[node_num]+1
            if c_to==p_col:
                c_to+=1
            c_min_list[node_num] = c_to
            c_mat[node_num][to] = c_to
            c_mat[to][node_num] = c_to
            dfs(to,node_num,c_to)



#計算，出力
dfs(0,-1,N)
K = max(c_min_list)+1
print(K)
for i in range(N-1):
    print(c_mat[A[i]-1][B[i]-1]+1)

### FIXED CODE ###

#Edgeの組を拾う時に，辞書が良いかも？
import sys
input = sys.stdin.readline

N = int(input())
E=[[] for _ in range(N)]

index ={}

for i in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    index[(a-1,b-1)]=i
    index[(b-1,a-1)]=i

K=0
#ここに答えを入れていく，
ans=[None]*(N-1)

#dfs,root=-1
#Q=[(node,pare)]
Q=[(0,-1)]
while(Q):
    node,p=Q.pop()
    col=1
    #根の時
    if p==-1:
        for to in E[node]:
            #ansの適切な位置に色情報を入れる
            ans[index[(node,to)]]=col
            col +=1
            K=max(col,K)
            Q.append((to,node))
    #根ではない時
    else:
        for to in E[node]:
            if to==p:
                continue
            #親の色と同じなら1を足す．
            col+=(col==ans[index[(node,p)]]) 
            ans[index[(node,to)]]=col
            col+=1
            K=max(col,K)
            Q.append((to,node))

print(K-1)
print(*ans,sep="\n")
s = int(input())

sm = sum([int(c) for c in s])
if s%sm == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
s=sum([i for i in map(int,str(n))])
if n % s == 0:
  print("Yes")
else:
  print("No")
s = input()
n = int(s)

if s[-1] != "9":
    n1 = n - int(s[-1]) +1
    s1 = str(n1)

ans1 = 0
for i in range(len(s1)):
    ans1 += int(s[i])

m = str(int(s[0]) - 1) + (len(s) - 1) * "9" 
ans2 = 0
for i in range(len(m)):
    ans2 += int(m[i])

print(max(ans1, ans2))

### FIXED CODE ###

s = input()
n = int(s)

m = str(int(s[0]) - 1) + (len(s) - 1) * "9" 
ans1 = 0
for i in range(len(m)):
    ans1 += int(m[i])

if s[-1] != "9" and n >= 10:
    n1 = n - (int(s[-1]) + 1)
    s = str(n1)

ans2 = 0
for i in range(len(s)):
    ans2 += int(s[i])

print(max(ans1, ans2))
a, b = raw_input().split(' ')
a = int(a)
b = int(b)
s = a * b
s2 = 2 * (a + b)
print("%d %d" % (s, s2))

### FIXED CODE ###

a, b = raw_input().split(' ')
a = int(a)
b = int(b)
s = a * b
s2 = 2 * (a + b)
print("%d %d" % (s, s2))
A, B, K = map(int, input().split())

if A >= B:
    L, S = A, B
if A < B:
    L, S = B, A

while L%S != 0:
    tmp = L;
    L = S;
    S = tmp%S;

gcd = int(S)

if gcd == 1:
    print(1)
    exit()

com_div = []
count = 1
while count < gcd:
    if gcd % count == 0:
        gcd = int(gcd / count)
        com_div.append(gcd)
        com_div.append(count)
    count += 1

com_div.sort(reverse=True)
print(com_div[K-1])


### FIXED CODE ###

A, B, K = map(int, input().split())

if A >= B:
    L, S = A, B
if A < B:
    L, S = B, A

while L%S != 0:
    tmp = L;
    L = S;
    S = tmp%S;

gcd = int(S)

if gcd == 1:
    print(1)
    exit()

com_div = []
com_div.append(gcd)
for i in range(1,gcd):
    if gcd % i == 0:
        com_div.append(i)

com_div.sort(reverse=True)
print(com_div[K-1])
box = []
box = input().split()
box[0], box[1] = box[1], box[0]
box[0], box[2] = box[2], box[0]
print(box[0] box[1] box[2])

### FIXED CODE ###

box = []
box = input().split()
box[0], box[1] = box[1], box[0]
box[0], box[2] = box[2], box[0]
print(box[0],  box[1],  box[2])
from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans += math.gcd(math.gcd(i,j), k)
      
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for g in range(1,k+1):
      ans += gcd(gcd(i,j), g)

print(ans)