Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than $k$ other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins.

Now each knight ponders: how many coins he can have if only he kills other knights?

You should answer this question for each knight.


-----Input-----

The first line contains two integers $n$ and $k$ $(1 \le n \le 10^5, 0 \le k \le \min(n-1,10))$ — the number of knights and the number $k$ from the statement.

The second line contains $n$ integers $p_1, p_2 ,\ldots,p_n$ $(1 \le p_i \le 10^9)$ — powers of the knights. All $p_i$ are distinct.

The third line contains $n$ integers $c_1, c_2 ,\ldots,c_n$ $(0 \le c_i \le 10^9)$ — the number of coins each knight has.


-----Output-----

Print $n$ integers — the maximum number of coins each knight can have it only he kills other knights.


-----Examples-----
Input
4 2
4 5 9 7
1 2 11 33

Output
1 3 46 36 
Input
5 1
1 2 3 4 5
1 2 3 4 5

Output
1 3 5 7 9 
Input
1 0
2
3

Output
3 


-----Note-----

Consider the first example.   The first knight is the weakest, so he can't kill anyone. That leaves him with the only coin he initially has.  The second knight can kill the first knight and add his coin to his own two.  The third knight is the strongest, but he can't kill more than $k = 2$ other knights. It is optimal to kill the second and the fourth knights: $2+11+33 = 46$.  The fourth knight should kill the first and the second knights: $33+1+2 = 36$. 

In the second example the first knight can't kill anyone, while all the others should kill the one with the index less by one than their own.

In the third example there is only one knight, so he can't kill anyone.

Difficulty: interview

Starter code:

Solutions:
n,m = map(int, input().split())

class Knight:
	def __init__(self, andis, p, c):
		self.p = int(p)
		self.c = int(c)
		self.andis = int(andis)
		self.ans = self.c

p = list(map(int, input().split()))
c = list(map(int, input().split()))
x = []
for i in range(n):
	x.append(Knight(i, p[i], c[i]))

x.sort(key=lambda x: x.p)
coins = []
for i in range(n-1):
	if len(coins) < m:
		coins.append(x[i].c)
		coins.sort()
	elif len(coins) > 0:
		if coins[0] < x[i].c:
			coins[0] = x[i].c
			coins.sort()
	x[i+1].ans += sum(coins)

x.sort(key=lambda x:x.andis)
for k in x:
	print(k.ans, end=' ')
	





_, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = list(sorted(zip(a, b, list(range(len(b))))))
d = [0] * len(b)

if k == 0:
    print(' '.join(map(str, b)))
else:
    best = [0] * k
    for pwr, cnt, index in c:
        d[index] = sum(best) + cnt

        if cnt > best[0]:
            for i in range(len(best)):
                if cnt <= best[i]:
                    best.insert(i, cnt)
                    best = best[1:]
                    break
            else:
                best = best[1:] + [cnt]


    print(' '.join(map(str, d)))


from math import ceil, log
from heapq import heappop, heappush, heapify
t = 1
for test in range(t):
    n,k = list(map(int, input().split()))
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    arr = [i for i in sorted(enumerate(p), key=lambda x:x[1])]
    maxcoins = [0 for i in range(k)]
    heapify(maxcoins)
    ans = list(p)
    tmpSum = 0
    tmpSum2 = 0
    prev = arr[0][1]
    for ind, power in arr:
        if power>prev:
            ans[ind] = tmpSum+c[ind]
            tmpSum2 = tmpSum
        else:
            ans[ind] = tmpSum2+c[ind]
        heappush(maxcoins, c[ind])
        tmpSum+=c[ind]
        tmpSum-=heappop(maxcoins)
    print(*ans)




    



#!/usr/bin/env python3

from heapq import heappop, heappush

[n, k] = list(map(int, input().strip().split()))
pis = list(map(int, input().strip().split()))
cis = list(map(int, input().strip().split()))

res = [0 for _ in range(n)]
nis = list(range(n))
nis.sort(key=lambda i: pis[i])

hc = []
l = 0
sc = 0

for i in nis:
	sc += cis[i]
	res[i] = sc
	heappush(hc, cis[i])
	if l == k:
		sc -= heappop(hc)
	else:
		l += 1

print(' '.join(map(str, res)))


n, k = [int(a) for a in input().split()]
power = [int(a) for a in input().split()]
coins = [int(a) for a in input().split()]

dp = [0 for i in range(n)]


def takeSecond(elem):
    return elem[1]


def takeFirst(elem):
    return elem[0]


people = [(power[i], coins[i], i) for i in range(n)]

people.sort(key=takeFirst)

dp[0] = []

for i, p in enumerate(people):
    if i == 0:
        continue
    kills = [i for i in dp[i - 1]]
    kills.append(people[i - 1][1])
    x = []

    if len(kills) > k:
        kills.remove(min(kills))

    dp[i] = kills

x = [(people[i][2], str(sum(dp[i]) + people[i][1])) for i in range(n)]

x.sort(key=takeFirst)

print(" ".join([z[1] for z in x]))


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

m = {}
for i in range( n ):
    if p[ i ] not in m:
        m[ p[ i ] ] = list()
    m[ p[ i ] ].append( c[ i ] )

a = {}
t = []
for key, val in sorted( m.items() ):
    a[ key ] = sum( t )
    t += val
    t.sort()
    t = t[ max( 0, len( t ) - k ) : len( t ) ]

print( " ".join( [ str( a[ p[ i ] ] + c[ i ] ) for i in range( n )]))


import heapq


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

p = list(map(int, input().strip().split()))
c = list(map(int, input().strip().split()))

p = sorted([(x, i) for i, x in enumerate(p)], key=lambda x: x[0])

ans = []
top_k = []

cur_gold = 0
for i, t in enumerate(p):
    if k == 0:
        ans.append((c[t[1]], t[1]))
    else:
        if i < k:
            cur_gold += c[t[1]]
            ans.append((cur_gold, t[1]))
            heapq.heappush(top_k, c[t[1]])
        else:
            smallest = heapq.nsmallest(1, top_k)[0]
            if smallest < c[t[1]]:
                cur_gold += c[t[1]]
                ans.append((cur_gold, t[1]))
                heapq.heappop(top_k)
                heapq.heappush(top_k, c[t[1]])
                cur_gold -= smallest
            else:
                ans.append((cur_gold + c[t[1]], t[1]))

ans = sorted(ans, key=lambda x: x[1])
print(" ".join(map(lambda x: str(x[0]), ans)))

import heapq
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))
indexes = sorted(list(range(n)), key=p.__getitem__)
most_vyg_odn_yye = []
res = [1]*n
cur_res = 0
for ind in indexes:
	this_cost = c[ind]
	heapq.heappush(most_vyg_odn_yye, this_cost)
	cur_res += this_cost
	res[ind] = cur_res
	if len(most_vyg_odn_yye) > k:
		cur_res -= heapq.heappop(most_vyg_odn_yye)
print(*res)


n, k = [int(i) for i in input().split()]
power = [int(i) for i in input().split()]
money = [int(i) for i in input().split()]

r = []
for i in range(n):
	r.append((power[i], money[i], i))

r.sort()
cur = 0


ans = [None for i in range(n)]

for i in range(k + 1):
	cur += r[i][1]
	ans[i] = cur

import heapq
pq = []
for i in range(k + 1):
	pq.append(r[i][1])
heapq.heapify(pq)

for i in range(k + 1, n):
	a = heapq.heappop(pq)
	ans[i] = ans[i - 1] - a + r[i][1]

	heapq.heappush(pq, r[i][1])

end = [None for i in range(n)]
for i in range(n):
	end[r[i][2]] = ans[i]

for i in range(n):
	end[i] = str(end[i])

print(" ".join(end))


n, k = [int(s) for s in input().split()]
p = [int(s) for s in input().split()]
p = [(p[i], i) for i in range(n)]

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

p.sort(key=lambda x: x[0], reverse=True)

c_dic = {}
for x in c:
    c_dic[x[1]] = x[0]

c.sort(key=lambda x: x[0], reverse=True)
ans_set = {}

used = set()
i = 0
cur_ans = 0
cur_k = 0
for j in range(n):
    x = p[j]
    if x[1] not in used:
        used.add(x[1])
    else:
        cur_k -= 1
        cur_ans -= c_dic[x[1]]

    while i < n:
        if cur_k == k:
            break
        if c[i][1] in used:
            i += 1
            continue

        cur_ans += c[i][0]
        cur_k += 1
        used.add(c[i][1])
        i += 1
    ans_set[x[1]] = cur_ans

for i in range(n):
    print(ans_set[i] + c_dic[i], end=" ")


import operator
class Knight:
    def __init__(self, power, coins, index):
        self.power = power
        self.coins = coins
        self.index = index

class MaxKnight:
    def __init__(self, coins, index):
        self.coins = coins
        self.index = index
nk = input().split(" ")
n = int(nk[0])
k = int(nk[1])

p = input().split(" ")
c = input().split(" ")
for i in range(n):
    p[i] = int(p[i])
    c[i] = int(c[i])
knights = []
for i in range(n):
    kn = Knight(p[i], c[i], i)
    knights.append(kn)
knights.sort(key=operator.attrgetter('power'))

max_c = []
max_knights = []
for i in range(n):
    max_knights.append(sum(max_c) + knights[i].coins)
    if len(max_c) < k:
        max_c.append(knights[i].coins)
    else:
        coins = knights[i].coins
        try:
            if coins > min(max_c):
                max_c.remove(min(max_c))
                max_c.append(coins)
        except:
            pass
# print(max_knights)
for i in range(n):
    max_knights[i] = MaxKnight(max_knights[i], knights[i].index)
max_knights.sort(key=operator.attrgetter('index'))
print(" ".join(str(knight.coins) for knight in max_knights))


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = list(map(int, input().split()))
for q in range(n):
    a[q] = [a[q], s[q], q]
a.sort()
b, d, z = [0]*k, 0, [[] for q in range(n)]
for q in range(n):
    z[a[q][2]] = d+a[q][1]
    l, j = 0, 0
    for q1 in range(k):
        if l == 1:
            b[q1], j = j, b[q1]
        elif a[q][1] > b[q1]:
            l, j = 1, b[q1]
            d += a[q][1] - b[-1]
            b[q1] = a[q][1]
print(*z)


n,k = tuple([int(x) for x in input().split(' ')])
p = list([int(x) for x in input().split(' ')])
c = list([int(x) for x in input().split(' ')])
out = [i for i in c]
#t = [(p[i], c[i]) for i in range(n)]
t = [(p[i], i) for i in range(n)]
import heapq
kbest = []
#print(t)
t.sort()
#print(t)
prev = 0
i = 0
while i < len(t):
    j = i
    while j < len(t) and t[j][0] == t[i][0] :
        out[t[j][1]] += sum(kbest)
        j += 1
    while i < j:
        heapq.heappush(kbest, c[t[i][1]])
        if len(kbest) > k:
            heapq.heappop(kbest)
        i += 1
"""
import bisect
for i in range(n):
    tp = (p[i], -1)
    it = bisect.bisect_left(t, tp)
    #print(it)
    aux = [tup[1] for tup in t[:it]]
    aux.sort()
    out[i] += sum(aux[-k:])
"""
print(' '.join([str(x) for x in out]))



import heapq

def main():
	n, k = map(int, input().split())
	power = list(map(int, input().split()))
	coins = list(map(int, input().split()))

	power_coins = sorted(zip(power, coins))
	result = {power[i]:coins[i] for i in range(n)}
	kills = 0
	coins = 0
	min_heap = []
	for p, c in power_coins:
		result[p] += coins
		if kills < k:
			kills += 1
			heapq.heappush(min_heap, c)
			coins += c
		elif k > 0:
			if c > min_heap[0]:
				coins -= min_heap[0]
				coins += c
				heapq.heapreplace(min_heap, c)
	print(' '.join(str(result[p]) for p in power))


main()

import heapq

n, k = [int(x) for x in input().strip().split()]
p = [int(x) for x in input().strip().split()]
c = [int(x) for x in input().strip().split()]

a = sorted(zip(p, c, list(range(n))))
coins = []
s = 0
ans = []

for ai in a:
    s += ai[1]
    ans.append([ai[2], s])
    heapq.heappush(coins, ai[1])
    if len(coins) > k:
        s -= heapq.heappop(coins)

print(*[c for i, c in sorted(ans)])


n, k = input().split(' ')
n = int(n)
k = int(k)
power2 = input().split(' ')
gold = input().split(' ')
prof = [0] * k
sums = dict()
s = 0
d = dict()
for i in range(n):
    power2[i] = int(power2[i])
    gold[i] = int(gold[i])
    d[power2[i]] = gold[i]
power = sorted(power2)
for i in range(n):
    ind = power[i]
    coin = d[ind]
    for j in range(k):
        if prof[j] >= coin:
            sums[ind] = s + coin
            prof.insert(j, coin)
            s = s - prof[0] + coin
            del prof[0]
            break
    else:
        sums[ind] = s + coin
        prof.append(coin)
        s = s - prof[0] + coin
        del prof[0]
st = ''
for elem in power2:
    st += str(sums[elem]) + ' '
print(st)

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
s = []
for i in range(n):
	s.append([i, p[i], c[i]])
s.sort(key = lambda x: x[1])
tk = 0
m = []
for i in range(n):
	coin = s[i][2] + sum(m)
	s[i].append(coin)
	if tk < k:
		m.append(s[i][2])
		tk += 1
	elif len(m) > 0:
		if min(m) < s[i][2]:
			m.remove(min(m))
			m.append(s[i][2])
s.sort()
for a in s:
	print(a[3], end=' ')


n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))
arr = [[p[i], i] for i in range(n)]
arr.sort()
z = []
ans = [0 for i in range(n)]
for i in range(n):
    s = 0
    for el in z:
        s += el
    ans[arr[i][1]] = s + c[arr[i][1]]
    z.append(c[arr[i][1]])
    z.sort()
    if len(z) > k:
        z = z[1:]
for el in ans:
    print(el, end=" ")


import array

n, k = list(map(int, input().split()))
p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
s = []
for i in range(n):
    s.append((i, p[i], c[i]))
s = sorted(s, key=lambda x: x[1])
sum_list = [[s[0][2]]]
sum_res = [s[0][2]]
for i in range(1, n):
    sum_list.append(list(sum_list[i-1]))
    if i-k-1 >= 0:
        sum_list[i].remove(min(sum_list[i]))
    sum_list[i].append(s[i][2])
    sum_res.append(sum(sum_list[i]))

ans = [str(x[1]) for x in sorted(enumerate(sum_res), key=lambda x: s[x[0]][0])]

print(" ".join(ans))


n,k=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
z=[x for x in range(n)]
zz=sorted(zip(x,y,z))
pre=[]
c=1
f=[0]*n
vv=0
#print(zz)
#print(pre)
ss=0
for i in range(n):
    if(i<k):
        pre.append(zz[i][1])
        gh=int(zz[i][2])
        f[gh]=ss+zz[i][1]
        ss+=zz[i][1]
    else:
        pre.sort()
        gh=int(zz[i][2])
        f[gh]=ss+zz[i][1]
        ff=False
        for j in range(0,len(pre)):
            if(zz[i][1]>pre[j]):
                ff=True
                ss=ss-pre[j]+zz[i][1]
                pre[j]=zz[i][1]
                break
print(*f)

# -*- coding: utf-8 -*-
"""
@Project : CodeForces
@File    : 2.py 
@Time    : 2018/6/17 0:27
@Author  : Koushiro 
"""


def __starting_point():
    n, k = map(int, input().split())
    knight = [[i,0,0,0]for i in range(n)]
    power = list(map(int, input().split()))
    money = list(map(int, input().split()))
    for i in range(n):
        knight[i][1]=power[i]
        knight[i][2]=money[i]
    knight.sort(key=lambda x:x[1])
    yong=[]
    yong_sum=0
    for i in range(n):
        knight[i][3]=knight[i][2]+yong_sum
        if len(yong)<k:
            yong.append(knight[i][2])
            yong.sort()
            yong_sum = sum(yong)
        elif k==0:
            continue
        else:
            if yong[0]<knight[i][2]:
                yong[0]=knight[i][2]
                yong.sort()
                yong_sum = sum(yong)

    knight.sort(key=lambda x:x[0])
    for i in range(n-1):
        print(knight[i][3], end="")
        print(" ", end="")
    print(knight[-1][3])
__starting_point()

from heapq import heapify, heappush, heappushpop

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

power = list(map(int , input().split()))
coins = list(map(int , input().split()))

knights = [i for i in range(n)]
knights.sort(key=lambda x:power[x])

cursum = 0
curcoin = []
heapify(curcoin)
res = [0] * n
for i in range(min(k,n)):
    res [knights[i]] = cursum +coins[knights[i]]
    heappush(curcoin, coins[knights[i]])
    cursum += coins[knights[i]]

for i in range(min(k,n), n):
    res [knights[i]] = cursum +coins[knights[i]]
    cursum += coins[knights[i]] - heappushpop(curcoin, coins[knights[i]])

print(*res)