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

import numpy as np
def main():
    A, B, N = map(int, input().split())
    max_value = 0
    if N < B:
        max_value = np.floor(A*N/B)
    else:
        for x in range(B+1):
            value = np.floor(A*x/B) - A * np.floor(x/B)
            #print(x, value)
            if value > max_value:
                max_value = value
    print(int(max_value))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
def main():
    A, B, N = map(int, input().split())
    max_value = 0
    x = np.min([B-1, N])
    max_value = int(np.floor(A*x/B))
    print(max_value)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
N = list(str(N))
N = [int(i) for i in N]

# print(N)
ans = 0
DP = [0] *2
DP[0] = 0
DP[1] = 1
for i in N:
    a, b = DP[0] ,DP[1]
    DP[0] = a + i if a+i < b +(10-i) else b +(10-i)
    DP[1] = a + i+1 if a + i+1 < b + (9-i) else b + (9-i)

    # print(DP)

print(DP[0] if DP[0] <= DP[1]+1 else DP[1] +1)

### FIXED CODE ###

N = list(map(int, input()))

# print(N)
ans = 0
DP = [0] *2
DP[0] = 0
DP[1] = 1
for i in N:
    a, b = DP[0] ,DP[1]
    DP[0] = a + i if a+i < b +(10-i) else b +(10-i)
    DP[1] = a + i+1 if a + i+1 < b + (9-i) else b + (9-i)

    # print(DP)

print(DP[0] if DP[0] <= DP[1]+1 else DP[1] +1)
### BUGGY CODE ###

def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def divi(n):
    ans = {1}
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ans |= l[i]
            ans |= l[n//i]
    ans.add(n)
    return ans

n = N()
cnt = 1
l = [{} for _ in range(n)]
l[1] = {1}
for i in range(2,n):
    #l[i] = make_divisors(i)
    l[i] = divi(i)
    cnt += len(l[i])

print(cnt)

### FIXED CODE ###

def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def divi(n):
    ans = {1}
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ans |= l[i]
            ans |= l[n//i]
    ans.add(n)
    return ans

n = N()
cnt = 1
l = [{} for _ in range(n)]
l[1] = {1}
tab = [0]*(n+1)
for i in range(1,n+1):
    for j in range(i, n + 1, i):
        tab[j] += 1
tab[n]=0
print(sum(tab))
### BUGGY CODE ###

# coding: utf-8
def binary_search(x, L2):
    l, r = 0, len(L2)-1
    mid = (r + l) // 2
    while r - l > 1:
        mid = (r + l) // 2
        if L2[mid] == x:
            break
        elif L2[mid] > x:
            l = mid
        elif L2[mid] < x:
            r = mid
    if L2[r] > c:
        return r
    else:
        return l
    # return r

N = int(input())
L = list(map(int, input().split()))
L.sort()
L = L[::-1]
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        c = a - b
        r = binary_search(c, L[j:]) + j
        if r > j and L[r] > c:
            ans += r - j
print(ans)

### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        ans += bisect_left(L, a+b) - 1 - j
print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
l=set(L)
ls=list(l)
#print(len(l))
ans=0
for i in range(len(l)):
    if L.count(ls[i])>ls[i]:
        ans+=L.count(ls[i])-ls[i]
    elif L.count(ls[i])<ls[i]:
        ans+=L.count(ls[i])
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=0
L=[0 for i in range(100005)]
for i in range(N):
    if A[i]<=100000:
        L[A[i]]+=1
    else:
        cnt+=1
    
for j in range(100002):
    
    if L[j]==j:
        pass
    elif L[j]<j:
        cnt+=L[j]
    elif L[j]>j:
        cnt+=L[j]-j
print(cnt)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = 1 + dp[i - 1][j] + dp[i][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD

ret = dp[n][m] + 1
if ret >= MOD:
    ret -= MOD
print(ret)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = (1 + dp[i - 1][j] + dp[i][j - 1]) % MOD
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD

print((dp[n][m] + 1) % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import copy

# input
N = int(input())
A = list()
for _ in range(N):
    A.append(int(input()))

# solve & output
for i in range(N):
    tmp = copy.copy(A)
    del tmp[i]
    print(max(tmp))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy

# input
N = int(input())
A = list()
for _ in range(N):
    A.append(int(input()))

# solve & output
ans = copy.copy(A)
ans.sort()
m = ans[-1]
for i in range(N):
    if A[i] != m:
        print(m)
    else:
        print(ans[N - 2])
### BUGGY CODE ###

mod =10**9 +7
n = int(input())
a = list(map(int, input().split()))
sumpro = 0

for i in range(n-1):
    x = 0
    for j in range(i+1, n):
        x += a[j]
    x = x%mod
    y = a[i]* x
    sumpro += y

print(sumpro%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

n,m,p = map(int, input().split())
edge = []
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
for i in range(n-1):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
ant1 = max(-dis[n],0)
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
ant2 = max(-dis[n],0)
if ant1 != ant2:
  print(-1)
else:
  print(ant1)

### FIXED CODE ###

n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

imos = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))


### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

imos = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    imos[p] += x

dq = deque([(0, -1)])
while dq:
    v, p = dq.popleft()
    for u in edge[v]:
        if u == p:
            continue
        imos[u] += imos[v]
        dq.append((u, v))

print(' '.join([str(x) for x in imos]))
### BUGGY CODE ###

s = input()
n = len(s)

a = [0]*2019
count = 0
for i in range(n):
    tmp = int(s[n-i-1:n]) % 2019
    count = count + a[tmp]
    a[tmp] = a[tmp] + 1
    if(tmp == 0):
        count = count + 1

print(count)

### FIXED CODE ###

s = input()[::-1]
n = len(s)

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

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

N = int(input())
S = list(input())

import itertools
lis = list(range(1, N+1))
c = 0

s = [1 for v in itertools.combinations(lis, 3)
     if v[1] - v[0] != v[2] - v[1] and S[v[0]-1] != S[v[1]-1] and S[v[0]-1] != S[v[2]-1] and S[v[1]-1] != S[v[2]-1]]

print(len(s))


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    N = int(input())
    S = list(input())
 
    c = [[] for _ in range(3)] #c = [[]] * 3 とすると全ての要素にappendされてしまうのでNG
    for i in range(len(S)):
        if S[i] == 'R':
            c[0].append(i)
        elif S[i] == 'G':
            c[1].append(i)
        else : # 'B'のとき
            c[2].append(i)
    total = len(c[0]) * len(c[1]) * len(c[2])

    reigai = 0 #先に条件2を満たすものを考えてから、条件1に当てはまるかを判定
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            k = j + (j - i)
            if k >= N:
                break
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                reigai += 1
    print(total - reigai)


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

N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 300001
for i in range(N):
  left, right = max(l[i]-K, 0), min(l[i]+K+1, 300000)
  cnts[l[i]] = max(cnts[left:right])+1
print(max(cnts))

### FIXED CODE ###

N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [1] * N
for i in range(N):
  for j in range(max(0, i-200), i):
    if abs(l[i]-l[j]) <= K:
      cnts[i] = max(cnts[i], cnts[j]+1)
print(max(cnts))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
S = sum(L)
A = [abs(2*sum(L[0:1])-S)]
for i in range(1,N):
  p = abs(2*sum(L[0:i])-S)
  if (p <= A[0]):
    del A[0]
    A.append(p)
print(A[0])

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
S = sum(L)
k = 0
ans = abs(2*sum(L[0:1])-S)
for i in range(0,N-1):
  k += L[i]
  ans = min(ans,abs(2*k-S))
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
  moji = input()
  if moji not in S:
    S.append(moji)
  
print(len(S))


### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  S.append(input())

print(len(set(S)))
### BUGGY CODE ###

import collections
N = int(input())

P = [0] * N
uvw = collections.deque()
for i in range(1, N):
    u, v, w = map(int, input().split())
    uvw.append((u, v, 0 if w % 2 == 0 else 1 ))

d = {}
u, v, w = uvw[0]
d[u] = 0

while len(uvw):
    u, v, w = uvw.popleft()
    if d.get(u, -1) >= 0:
        d[v] = d[u] ^ w
        continue
    elif d.get(v, -1) >= 0:
        d[u] = d[v] ^ w
        continue
    uvw.append((u, v, w))

for i in range(1, N+1):
    print(d[i])

### FIXED CODE ###

import collections
N = int(input())

g = [dict() for _ in range(N+1)]
for i in range(1, N):
    u, v, w = map(int, input().split())
    w = 0 if w % 2 == 0 else 1
    g[u][v] = w
    g[v][u] = w

ret = {1:0}
q = collections.deque()
q.append(1)
while len(q):
    d = q.pop()
    for h in g[d]:
        if ret.get(h, -1) < 0:
            ret[h] = ret[d] ^ g[d][h]
            q.append(h)

for i in range(1, N+1):
    print(ret[i])
### BUGGY CODE ###

# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
H,W = map(int,input().split())
S = [input().rstrip() for _ in range(H)]

LR = [[0 for _ in range(W)] for _ in range(H)]
UD = [[0 for _ in range(W)] for _ in range(H)]

# 横方向
for h in range(H):
    cnt = 0
    for w in range(W):
        if S[h][w] == "#":
            cnt = 0
        else:
            cnt += 1
        LR[h][w] = cnt
for h in range(H):
    cnt = 0
    for w in range(W):
        if LR[h][W-1-w] == 0:
            cnt = 0
        else:
            if cnt==0:
                cnt = LR[h][W-1-w]
            else:
                LR[h][W-1-w] = cnt

# 縦方向
for w in range(W):
    cnt = 0
    for h in range(H):
        if S[h][w] == "#":
            cnt = 0
        else:
            cnt += 1
        UD[h][w] = cnt
for w in range(W):
    cnt = 0
    for h in range(H):
        if UD[H-1-h][w] == 0:
            cnt = 0
        else:
            if cnt==0:
                cnt = UD[H-1-h][w]
            else:
                UD[H-1-h][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, LR[h][w] + UD[h][w] - 1)

print(ans)

### FIXED CODE ###

# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
H,W = map(int,input().split())
S = [input().rstrip() for _ in range(H)]

LR = [[0 for _ in range(W)] for _ in range(H)]
UD = [[0 for _ in range(W)] for _ in range(H)]

# 横方向
for h in range(H):
    cnt = 0
    for w in range(W):
        if S[h][w] == "#":
            cnt = 0
        else:
            cnt += 1
        LR[h][w] = cnt
for h in range(H):
    cnt = 0
    for w in range(W):
        if LR[h][W-1-w] == 0:
            cnt = 0
        else:
            if cnt==0:
                cnt = LR[h][W-1-w]
            else:
                LR[h][W-1-w] = cnt

# 縦方向
for w in range(W):
    cnt = 0
    for h in range(H):
        if S[h][w] == "#":
            cnt = 0
        else:
            cnt += 1
        UD[h][w] = cnt
for w in range(W):
    cnt = 0
    for h in range(H):
        if UD[H-1-h][w] == 0:
            cnt = 0
        else:
            if cnt==0:
                cnt = UD[H-1-h][w]
            else:
                UD[H-1-h][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, LR[h][w] + UD[h][w] - 1)

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

N = int(input())
A = list(map(int,input().split()))
s = 1
for a in A:
    s *= a
if s>10**(18):
    print(-1)
else:
    print(s)


### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
s = 1
if 0 in A:
    print(0)
    exit(0)
for i in A:
    s *= i
    if s > 10**(18):
        print(-1)
        exit(0)
print(s)
### BUGGY CODE ###

import functools
import numpy as np

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

x.append(X)
x = np.array(x)
min_x = np.array([min(x) for _ in range(n+1)])
x = (sorted(x) - min_x)[1:]


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


if n > 1:
    ans = euclid(x[0], x[1])


    for xi in x[2:]:
        ans = euclid(ans, xi)
        if ans == 1:
            break

else:
    ans = x[0]

print(ans)


### FIXED CODE ###

import functools
import numpy as np

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


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


if n > 1:
    if abs(x[0]-X) == 0:
        ans = euclid(abs(x[1]-X), abs(x[2]-X))
    elif abs(x[1]-X) == 0:
        ans = euclid(abs(x[0]-X), abs(x[2]-X))
    else:
        ans = euclid(abs(x[0]-X), abs(x[1]-X))

    for xi in x[2:]:
        ans = euclid(ans, abs(xi-X))
        if ans == 1:
            break

else:
    ans = abs(x[0] - X)

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

n = int(input())
s = input()

dp = [[0] * (n + 1) for _ in range(n + 1)]

res = 0
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)


### FIXED CODE ###

n = int(input())
s = input()

dp = [[0] * (n + 1) for _ in range(n + 1)]

res = 0
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
            # dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)
### BUGGY CODE ###

def add(s1,s2):
    l = []
    for i in range(len(s1)):
        for j in range(len(s2)):
            l.append(s1[i]+s2[j])
    return l

def cake(s1,s2,s3):
    ans1 = add(s1,s2)
    ans2 = add(ans1,s3)
    return ans2    
    
a,b,c,d = map(int, input().split())
s1=list(map(int, input().split()))
s2=list(map(int, input().split()))
s3=list(map(int, input().split()))
z = sorted(cake(s1,s2,s3),reverse=True)
for i in range(0,d):
    print(z[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
x, y, z, k = map(int, input().split())
a = sorted(int(i) for i in input().split())
b = sorted(int(i) for i in input().split())
c = sorted(int(i) for i in input().split())
 
#a.sort(reverse=True)
#b.sort(reverse=True)
#c.sort(reverse=True)
 
ab = sorted(i+j for i in a for j in b)[:-k-1:-1]
abc = sorted(i+j for i in ab for j in c)[:-k-1:-1]
 
print(*abc[:k], sep="\n")
### BUGGY CODE ###

S = input()
n = 0
import re
while 'BW' in S:
    re.sub('BB+',"BB",S)
    re.sub("WW+",'WW',S)
    n += S.count('BW')
    S = S.replace('BW','WB')
print(n)

### FIXED CODE ###

S = input()
n = 0
k = 0
m = len(S)
for i in range(m):
    if S[i] == 'B':
        n += m - (i+1) -k
        k += 1
print(n)
### BUGGY CODE ###

import math

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義
    
def list_gcd(x):
    if len(x) == 1:
        return x[0]
    next_list = []
    for i in range(int(len(x)/2)):
        next_list.append(gcd(x[2*i],x[2*i+1]))
    if len(x)%2 == 1:
        next_list.append(x[-1])
    
    return list_gcd(next_list)

out = 0
for i in range(len(A)):
    l = A[:i] + A[i+1:]
    this_gcd = list_gcd(l)
    if this_gcd > out:
        out = this_gcd
        
print(out)

### FIXED CODE ###

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義
    
list_gcd = [(gcd(A[0],A[1]),False),(A[0],True),(A[1],True)]
#print(list_gcd)

for i in range(2,len(A)):
    next_gcd = []
    for j in list_gcd:
        if j[1]:
            this_gcd = (gcd(j[0],A[i]),True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
        else:
            this_gcd = (gcd(j[0],A[i]),False)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
                
            this_gcd = (j[0],True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
    list_gcd = next_gcd
    #print(list_gcd)
         
out = 1
for i in list_gcd:
    if i[0] > out:
        out = i[0]
        
print(out)
### BUGGY CODE ###

from bisect import insort
n,k,*td=map(int,open(0).read().split())
td = [[t,d] for t,d in zip(td[::2],td[1::2])]
td = sorted(td,key = lambda x:x[1],reverse=True)

score = [0] * k
taste_sum = 0
extra_taste = []
eat_num = 0
eat_kind = set()

for t,d in td:
    if t in eat_kind:
        if eat_num == k:
            continue
        else:
            insort(extra_taste, d)
            eat_num += 1
    else:
        eat_kind.add(t)
        taste_sum += d
        eat_num += 1
        if eat_num > k:
            eat_num -= 1
            extra_taste = extra_taste[1:]
    
    if eat_num == k:
        score[len(eat_kind)-1] = len(eat_kind)**2 + taste_sum + sum(extra_taste)
            
    if len(eat_kind) == k:
        break
print(max(score))

### FIXED CODE ###


import heapq

n,k,*td=map(int,open(0).read().split())
td = [[t,d] for t,d in zip(td[::2],td[1::2])]
td = sorted(td,key = lambda x:x[1],reverse=True)

score = [0] * k
taste_sum = 0
extra_taste = []
eat_num = 0
eat_kind = set()

for t,d in td:
    if t in eat_kind:
        if eat_num == k:
            continue
        else:
            heapq.heappush(extra_taste, d)
            taste_sum += d
            eat_num += 1
    else:
        eat_kind.add(t)
        taste_sum += d
        eat_num += 1
        if eat_num > k:
            eat_num -= 1
            taste_sum -= heapq.heappop(extra_taste)
    
    if eat_num == k:
        score[len(eat_kind)-1] = len(eat_kind)**2 + taste_sum
            
    if len(eat_kind) == k:
        break
print(max(score))
### BUGGY CODE ###

from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(r):
        ans*=(n-i)
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = []
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x.append(a%2019)
c=Counter(x)
cc=c.most_common()
ans = c[0]
for i in range(len(cc)):
    ans += combi(cc[i][1],2)

print(ans)


### FIXED CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

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

import numpy as np
N = int(input())
G = np.zeros((N,N),dtype = np.bool)

pairs = []

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

Cs = list(sorted(map(int,input().split())))


links = [0 for i in range(N)]

for i in range(N):
    links[i] = G[i,:].sum()

nodeval = np.array([0 for i in range(N)])

# print(links)

disabled = [False for i in range(N)]
while len(Cs) > 0:
    mx = 0
    for i,l in enumerate(links):
        if not disabled[i]:
            mx = max(l,mx)
    # print("mx",mx, "da", disabled)
    for i,l in enumerate(links):
        if not disabled[i] and l == mx:
            break
    disabled[i] = True
    # max connected node
    # print(i)
    nodeval[i] = Cs.pop(-1)

# print(nodeval)

sumval = 0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")


### FIXED CODE ###

import numpy as np 
N = int(input())
# N = 1000
# G = np.zeros((N,N),dtype = np.bool)

linked = [[] for i in range(N)]
pairs = []

for i in range(N-1):
    a,b = map(int,input().split())
    # a,b = 1,2
    pairs.append((a,b))
    linked[a-1].append(b-1)
    linked[b-1].append(a-1)

Cs = list(sorted(map(int,input().split()),reverse=True))
# Cs = [1 for i in range(N)]

# print(Cs)

links = np.array([0 for i in range(N)])

for i in range(N):
    links[i] = len(linked[i])

# minag = np.argmin(links)
nodeval = np.array([0 for i in range(N)])

stack = [1]

visited = [False for i in range(N)]

while(len(stack)>0):
    minag = stack.pop()
    nodeval[minag] = Cs.pop(0)
    for l in linked[minag]:
        if not visited[l]:
            stack.append(l)
    visited[minag] = True
    # print(nodeval)

sumval=0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")