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

import bisect
import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

if n == 1:
    ans = max((a[0] - k) * f[0], 0)
    print(ans)

else:
    a.sort()
    f.sort(reverse=True)
    s = []
    t = []
    for x,y in zip(a,f):
        s.append((x*y, y))
    s.sort()

    while len(s) > 1:
        t.append(s[-1])
        tmp = 0
        for l, y in t:
            tmp += max(1, math.ceil((l - s[-2][0]) / y))
        if k <= tmp:
            t = t[:-1]
            break
        s = s[:-1]
    
    for l, y in t:
        tmp = max(1, math.ceil((l - s[-1][0]) / y))
        k -= tmp
        l -= tmp * y
        bisect.insort(s, (l, y))
    
    while k > 0 and s[-1][0] > 0:
        l, y = s[-1]
        s = s[:-1]
        tmp = math.ceil((l - s[-1][0]) / y)
        if tmp == 0:
            tmp = 1
        if k > tmp:
            k -= tmp
        else:
            tmp = k
            k = 0
        l = l - tmp * y
        bisect.insort(s, (l, y))
    print(s[-1][0])


### FIXED CODE ###

import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

a.sort()
f.sort(reverse=True)

low = 0
high = 0
for x, y in zip(a,f):
    high = max(high, x*y)

while high != low:
    test = int((high + low) // 2)
    tmp = 0
    for x, y in zip(a,f):
        tmp += max(0, x - math.floor(test / y))
        if tmp > k:
            low = test + 1
            break
    else:
        high = test
print(high)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]


def knapzap(N, A, B) :
    dp = [0] * (N + 1)
    n_ = 0
    A_, B_ = [], []
    for a, b in zip(A, B) :
        if a < b :
            A_.append(a)
            B_.append(b)
            n_ += 1

    for n in range(1, N + 1) :
        dp[n] = max([dp[n-1] + 1] + [dp[n-A_[i]] + B_[i] if n - A_[i] >= 0  else 0 for i in range(n_)])

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

def knapzap(N, A, B) :
    dp = [0] * (N + 1)

    for n in range(1, N + 1) :
        dp[n] = max(
            dp[n-1] + 1,
            dp[n-A[0]] + B[0] if n - A[0] >= 0 else 0,
            dp[n-A[1]] + B[1] if n - A[1] >= 0 else 0,
            dp[n-A[2]] + B[2] if n - A[2] >= 0 else 0
        )

    return dp[N]

M = knapzap(N, A, B)
ret = knapzap(M, B, A)
print(ret)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
ans=0
mod=10**9+7
for i in range(1,61):
   zero,one=0,0
   for j in S:
      tmp=bin(j)[2:]
      tmp=tmp.zfill(60)
      if tmp[-i]=="1":
         one+=1
      else:
         zero+=1
   s=pow(2,i-1,mod)
   ans+=s*zero*one%mod
   ans%=mod
print(ans)

### FIXED CODE ###

import numpy as np 
N=int(input())
a=np.array(list(map(int, input().split())))
ans=0
mod=10**9+7
for i in range(60):
   s=np.count_nonzero(a>>i&1)
   ans+=pow(2,i,mod)*s*(N-s)%mod
   ans%=mod
print(ans)
### BUGGY CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
def f(K):
    L=deque()
    L.append([0,A[0]])
    for i in range(N-1):
        #print(L)
        if A[i]<A[i+1]:
            L.append([0,A[i+1]-A[i]])
            continue
        t=A[i]-A[i+1]
        while t-L[-1][1]>=0:
            t-=L[-1][1]
            L.pop()
            #print(L)
        L[-1][1]-=t
        #if L[-1][1]==0:
            #L.pop()
        if L[-1][0]!=K-1:
            if L[-1][1]==1:
                L[-1][0]+=1
            else:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
        else:
            s=0
            while len(L)!=0 and L[-1][0]==K-1:
                s+=L[-1][1]
                L.pop()
            if len(L)==0:
                return False
            elif L[-1][1]==1:
                L[-1][0]+=1
                L.append([0,s])
            elif L[-1][1]!=1:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
                L.append([0,s])
    #print(L)
    return True



mi=0
ma=2*10**5+1
while ma-mi>1:
    mid=(ma+mi)//2
    if f(mid):
        ma=mid
    else:
        mi=mid
print(ma)


### FIXED CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
def f(K):
    L=deque()
    L.append([0,A[0]])
    for i in range(N-1):
        #print(L)
        if A[i]<A[i+1]:
            L.append([0,A[i+1]-A[i]])
            continue
        t=A[i]-A[i+1]
        while t-L[-1][1]>=0:
            t-=L[-1][1]
            L.pop()
            #print(L)
        L[-1][1]-=t
        #if L[-1][1]==0:
            #L.pop()
        if L[-1][0]!=K-1:
            if L[-1][1]==1:
                L[-1][0]+=1
            else:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
        else:
            s=0
            while len(L)!=0 and L[-1][0]==K-1:
                s+=L[-1][1]
                L.pop()
            if len(L)==0:
                return False
            elif L[-1][1]==1:
                L[-1][0]+=1
                L.append([0,s])
            elif L[-1][1]!=1:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
                L.append([0,s])
    #print(L)
    return True



mi=0
ma=2*10**5+1
while ma-mi>1:
    mid=(ma+mi)//2
    if f(mid):
        ma=mid
    else:
        mi=mid
print(ma)
### BUGGY CODE ###

n = int(input()) 
l = list(map(int, input().split()))
if l[0] != 0:
    print(0)
    exit()

max_vertex = max(l)
ll = []

for i in range(1, max_vertex+1):
    if l.count(i) == 0:
        print(0)
        exit()
    ll.append(l.count(i))

count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)

### FIXED CODE ###

n = int(input()) 
l = list(map(int, input().split()))
if l[0] != 0:
    print(0)
    exit()

for i in range(1, n):
    if l[i] == 0:
        print(0)
        exit()

max_vertex = max(l)
ll = []
l=sorted(l)
l.append(-4)
c=1
for i in range(1, n):
    if l[i] != l[i+1]:
        if l[i] != l[i+1]-1 and l[i+1] > 0:
            print(0)
            exit()
        ll.append(c)
        c = 0
    c+=1

count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)
### BUGGY CODE ###


value = list(input())
res = 0
while len(value) != 1 and len(value) != 0:
    zero = value[0]
    one = value[-1]
    if zero == one:
        value.pop(0)
        value.pop()
    else:
        if zero != "x" and one != "x":
            res = -1
            break
        value.extend("x") if zero == "x" else value.insert(0, "x")
        value.pop(0)
        value.pop()
        res += 1
print(res)


### FIXED CODE ###

s = input()
ns = s.replace('x', '')
if s == s[::-1]:
    print(0)
elif ns != ns[::-1]:
    print(-1)
else:
    cnt = 0
    i = 0
    j = len(s)-1
    while(i<j):
        if s[i]=='x' and s[j]!='x':
            cnt += 1
            j += 1
        elif s[i]!='x' and s[j]=='x':
            cnt += 1
            i -= 1
        i += 1
        j -= 1
    print(cnt)
### BUGGY CODE ###

input_s = input()
len_s = len(input_s)
ans = 0

for i in range(len_s - 4):
    for j in range(i+3, len_s):
        if (int(input_s[i:j+1]) % 2019) == 0:
            ans += 1

print(ans)


### FIXED CODE ###

s = input()[::-1]
n = len(s)
x = 1
tot = 0 # 累積和
cnt = [0 for i in range(2019)] # 累積和の値になる個数

ans = 0
for i in range(n):
    # print('======={}======'.format(i))
    cnt[tot] += 1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    # print(tot)
    ans += cnt[tot]
    # print('ans:', ans)
    x = x*10%2019

print(ans)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, a, b, c = [int(i) for i in input().split()]
L = [int(input()) for i in range(n)]

INF = 10 ** 9

def dfs(i, L, A):
    if all(a == 0 for a in A):
        return 0
    if n - L.count(0) < 3:
        return INF
    if i == n:
        return INF
    if L[i] == 0:
        return dfs(i+1, L[:], A[:])
    for j, a in enumerate(A):
        if a == L[i]:
            A[j] = 0
            return dfs(i+1, L[:], A[:])

    res = dfs(i+1, L[:], A[:])
    for j, a in enumerate(A):
        if a == 0:
            continue
        TL = L[:i] + [a] + L[i+1:]
        TA = A[:j] + [0] + A[j+1:]
        d = abs(L[i] - a)
        res = min(res, dfs(i+1, TL, TA) + d)

    for j in range(i+1, n):
        if L[j] == 0:
            continue
        TL = L[:]
        TL[i] += TL[j]
        TL[j] = 0
        res = min(res, dfs(i, TL, A[:]) + 10, dfs(i+1, TL, A[:]) + 10)

    return res

print(dfs(0, L[:], [a, b, c]))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

N, A, B, C = [int(i) for i in input().split()]
L = [int(input()) for i in range(N)]

INF = 10 ** 9

def dfs(n, a, b, c):
    if n == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a, b, c) > 0 else INF
    res = dfs(n+1, a+L[n], b, c) + 10
    res = min(res, dfs(n+1, a, b+L[n], c) + 10)
    res = min(res, dfs(n+1, a, b, c+L[n]) + 10)
    res = min(res, dfs(n+1, a,  b, c))

    return res

print(dfs(0, 0, 0, 0))
### BUGGY CODE ###

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

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                count += 1
print(count)

### FIXED CODE ###

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

count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <=K:
            count += 1

print(count)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
dp=np.zeros((N+1,3))

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:

                dp[i][j] = max(dp[i-1][k] + S[i-1][j],dp[i][j])
                #happy =  dp[i-1][k] + S[i-1][j]
                #if dp[i][j] < happy:
                #    dp[i][j] = happy

print(int(max(dp[N])))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    D = list(map(int, input().split()))
    S.append(D)

import numpy as np
#dp=np.zeros((N+1,3))

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                happy =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

s = input()
q = s.count("?")
# 先頭i文字で数えられるもののうちあまりがjであるものの数
dp = [[0 for _ in range(13)] for _ in range(len(s))]

for i, v in enumerate(s):
    if i == 0:
        if v == '?':
            for j in range(10):
                dp[0][j] += 1
        else:
            dp[0][int(v)] += 1
    else:
        for j in range(13):
            if v == '?':
                for k in range(10):
                    dp[i][(10 * j + k) % 13] += dp[i-1][j]
            else:
                dp[i][(10 * j + int(v)) % 13] += dp[i - 1][j]

    for j in range(13):
        dp[i][j] = dp[i][j] % 1000000007

print(dp[len(s)-1][5])

### FIXED CODE ###

s = input()
q = s.count("?")
ans = [0] * 13
ans[0] = 1

for v in s:
    dp = [0] * 13
    for j in range(13):
        dp[(j * 10) % 13] = ans[j] % 1000000007
    dp += dp
    for j in range(13):
        if v == '?':
            ans[j] = sum(dp[j+4:j+14])
        else:
            ans[j] = dp[j - int(v)]

print(ans[5] % 1000000007)
### BUGGY CODE ###

import sys
n,k = map(int,input().split())
a = abs(n-k)
if n < a:
    print(n)
    sys.exit()
while True:
    a = abs(a-k)
    if n < a:
        print(a)
        break
    else:
        continue

### FIXED CODE ###

n, k = map(int, input().split()) 
t = n % k
if (k-t > t):
    print(t)
else:
    print(k-t)
### BUGGY CODE ###

import heapq
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]

heapq.heapify(a)
for i in range(m) :
    B = b[i][0]
    C = b[i][1]
    for j in range(B) :
        if a[0] < C :
            heapq.heappop(a)
            heapq.heappush(a,C)
        else :
            break
 
print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]
a.sort()
b = sorted(b,key = lambda  x: x[1],reverse=True)
d = []
j = 0
while (n<=len(a) or j<m) :
    C = b[j][1]
    B = b[j][0]
    for i in range(B) :
        d.append(C)
    j += 1
    if j>=m or len(d) > len(a) :
        break

for i in range(min(len(d),len(a))) :
    if a[i] < d[i] :
        a[i] = d[i]

print(sum(a))
### BUGGY CODE ###

import itertools
T = input()
TC = list(T)
N = [i for i, x in enumerate(TC) if x == '?']
B = list(itertools.product(['P','D'], repeat=len(N)))
point = [0]*len(B)
strs = ['']*len(B)
for b,i in zip(B,range(len(B))):
    TC = list(T)
    for n,j in zip(N,range(len(N))):
        TC[n] = b[j]
    TC = ''.join(TC)
    strs[i] = TC
    point[i] = TC.count('PD') + TC.count('D')
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
#まずk学期までの
p=1
for i in range(k):
    p*=a[i]
    p//(10**9 +7)


for i in range(n-k):
    tmp=p
    p//=a[i]
    p*=a[i+k]
    p//(10**9 +7)
    #print(p)
    if p>tmp:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

for i in range(n-k):

    if a[i]<a[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [i % (10**9 + 7) for i in a]
ans = 0
for i in range(n - 1):
    ans += a[i]*(sum(a[i+1:])%(10**9 + 7))
    ans %= 10**9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [i % (10**9 + 7) for i in a]
val = sum(a[1:])
l = [val]
for i in range(1, n):
    val -= a[i]
    l.append(val)
ans = 0
for i in range(n - 1):
    ans += a[i]*l[i]
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

h,n=map(int,input().split())
INF=10**9
A=[]; dp=[INF]*(h+10)
for i in range(n):
  x,y=map(int,input().split())
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h):
    if dp[i]==INF: continue
    index=min(h,i+a)
    dp[index]=min(dp[index],dp[i]+b)
print(dp[h])


### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

d1 = int(input())
d = input().split()
d2 = [int(x) for x in d]
count=0
for n in range(d1):

    for m in range(n+1,d1):
        if d2[n] == d2[m]:
            count+=1


if count==0  :
    print("YES")
else:
    print("NO")

    

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
if N == len(set(A)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

lin = []
li0 = []
for i in range(n):
    lin.append(set())
    li0.append(set())
for i in range(m):
    lin[s[i][0] - 1].add(s[i][2])
    li0[s[i][1] - 1].add(s[i][2])
for i in range(n - 1):
    li0[i + 1] = li0[i + 1] | li0[i]
for i in range(n - 1, 0, -1):
    lin[i - 1] = lin[i] | lin[i - 1]
for i in range(q):
    ans = len(lin[t[i][0] - 1] & li0[t[i][1] - 1])
    print(ans)

### FIXED CODE ###

#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

LR = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for v in range(m):
     LR[s[v][0]][s[v][1]] += 1

for j in range(1, n + 1):
    for i in range(1, n + 1):#Lについての累積和
        LR[i][j] += LR[i - 1][j]
for i in range(1, n + 1):
    for j in range(1, n + 1):#Rについての累積和，2次元累積和にする
        LR[i][j] += LR[i][j - 1]

for k in range(q):
    tmp = 0
    #for j in range(t[k][0], t[k][1] + 1):#Rについてみていく
        #tmp += LR[t[k][1]][j] - LR[t[k][0] - 1][j]
    tmp += (LR[t[k][1]][t[k][1]] - LR[t[k][1]][t[k][0] - 1]) - (LR[t[k][0] - 1][t[k][1]] - LR[t[k][0] - 1][t[k][0] - 1])

    print(tmp)
### BUGGY CODE ###

n,k = map(int,input().split())
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
ans = 10 ** 40
for i in range(n):
    for j in range(n):
        for l in range(n):
            for h in range(n):
                lx = min(x[i],x[j])
                rx = max(x[i],x[j])
                uy = max(y[l],y[h])
                dy = min(y[l],y[h])
                cnt = 0
                for ii in range(n):
                    if lx <= x[ii] <= rx and dy <= y[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = 0
start = 0

while ( start < N ):
    tmp_ans = 0
    for j in range(start, N-1):
        if (H[j] >= H[j+1]):
            tmp_ans += 1
        else:
            start += tmp_ans
            break
            
    ans = max(ans, tmp_ans)
    start += 1
    
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = [0]

for i in range(0, len(H)-1):
    if (H[i] >= H[i+1]):
        ans.append(ans[i]+1)
    else:
        ans.append(0)

print(max(ans))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

def summention(n):
    return n*(n+1)//2

n = int(input())
print(summention(n-1))
### BUGGY CODE ###

def main():
    B_MAX = (80 + 80 - 1) * 80
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(min(B_MAX, max_b) + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    B_MAX = (80 + 80 - 1) * 80 // 2
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(min(B_MAX, max_b) + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


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

import math
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 k in range(1,K+1):
            ans += gcd(gcd(i,j),k)
print(ans)
### BUGGY CODE ###

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
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  for j in range(i, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

### FIXED CODE ###

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)
    return divisors
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  b = n // d[i]
  if b == d[i]:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if b == d[j]:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)