{"raw_statement":[{"iden":"statement","content":"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.\n\nNow each knight ponders: how many coins he can have if only he kills other knights?\n\nYou should answer this question for each knight."},{"iden":"input","content":"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.\n\nThe 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.\n\nThe 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."},{"iden":"output","content":"Print $n$ integers — the maximum number of coins each knight can have it only he kills other knights."},{"iden":"examples","content":"Input\n\n4 2\n4 5 9 7\n1 2 11 33\n\nOutput\n\n1 3 46 36 \n\nInput\n\n5 1\n1 2 3 4 5\n1 2 3 4 5\n\nOutput\n\n1 3 5 7 9 \n\nInput\n\n1 0\n2\n3\n\nOutput\n\n3"},{"iden":"note","content":"Consider the first example.\n\n*   The first knight is the weakest, so he can't kill anyone. That leaves him with the only coin he initially has.\n*   The second knight can kill the first knight and add his coin to his own two.\n*   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$.\n*   The fourth knight should kill the first and the second knights: $33+1+2 = 36$.\n\nIn 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.\n\nIn the third example there is only one knight, so he can't kill anyone."}],"translated_statement":[{"iden":"statement","content":"与圆桌骑士不同，多边形桌骑士失去了贵族身份，乐于互相残杀。但每个骑士都有一定的力量，只有当一个骑士的力量大于受害者的力量时，他才能杀死另一个骑士。然而，即使这样的骑士也会受到良心的折磨，因此他最多只能杀死 $k$ 个其他骑士。此外，每个骑士都有一些金币。在杀死一个骑士后，该骑士可以夺取受害者所有的金币。\n\n现在每个骑士都在思考：如果仅由他来杀死其他骑士，他最多能拥有多少金币？\n\n你需要为每个骑士回答这个问题。\n\n第一行包含两个整数 $n$ 和 $k$ $(1 lt.eq n lt.eq 10^5, 0 lt.eq k lt.eq min (n -1, 10))$ —— 骑士的数量和题目中提到的 $k$。\n\n第二行包含 $n$ 个整数 $p_1, p_2, dots.h, p_n$ $(1 lt.eq p_i lt.eq 10^9)$ —— 每个骑士的力量。所有 $p_i$ 互不相同。\n\n第三行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$ $(0 lt.eq c_i lt.eq 10^9)$ —— 每个骑士拥有的金币数量。\n\n请输出 $n$ 个整数 —— 每个骑士仅通过杀死其他骑士所能获得的最大金币数。\n\n考虑第一个例子。\n\n在第二个例子中，第一个骑士无法杀死任何人，而其他所有骑士都应杀死编号比自己小一的骑士。\n\n在第三个例子中，只有一个骑士，因此他无法杀死任何人。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $k$ $(1 lt.eq n lt.eq 10^5, 0 lt.eq k lt.eq min (n -1, 10))$ —— 骑士的数量和题目中提到的 $k$。第二行包含 $n$ 个整数 $p_1, p_2, dots.h, p_n$ $(1 lt.eq p_i lt.eq 10^9)$ —— 每个骑士的力量。所有 $p_i$ 互不相同。第三行包含 $n$ 个整数 $c_1, c_2, dots.h, c_n$ $(0 lt.eq c_i lt.eq 10^9)$ —— 每个骑士拥有的金币数量。"},{"iden":"output","content":"请输出 $n$ 个整数 —— 每个骑士仅通过杀死其他骑士所能获得的最大金币数。"},{"iden":"examples","content":"输入\n4 2\n4 5 9 7\n1 2 11 33\n输出\n1 3 46 36\n\n输入\n5 1\n1 2 3 4 5\n1 2 3 4 5\n输出\n1 3 5 7 9\n\n输入\n1 0\n23\n输出\n3 "},{"iden":"note","content":"考虑第一个例子。\n\n第一个骑士最弱，因此他无法杀死任何人。他只能保留自己初始拥有的1枚金币。\n\n第二个骑士可以杀死第一个骑士，并将他的1枚金币加到自己的2枚上。\n\n第三个骑士最强，但他最多只能杀死 $k = 2$ 个其他骑士。最优策略是杀死第二个和第四个骑士：$2 + 11 + 33 = 46$。\n\n第四个骑士应杀死第一个和第二个骑士：$33 + 1 + 2 = 36$。\n\n在第二个例子中，第一个骑士无法杀死任何人，而其他所有骑士都应杀死编号比自己小一的骑士。\n\n在第三个例子中，只有一个骑士，因此他无法杀死任何人。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n $ be the number of knights.\n- Let $ k \\in \\mathbb{Z}_{\\geq 0} $, $ k \\leq \\min(n-1, 10) $, be the maximum number of knights a knight can kill.\n- Let $ \\mathbf{p} = (p_1, p_2, \\dots, p_n) \\in \\mathbb{Z}_{>0}^n $ be the distinct power values of the knights.\n- Let $ \\mathbf{c} = (c_1, c_2, \\dots, c_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be the coin values of the knights.\n\n**Given:**\n\n- Knight $ i $ can kill knight $ j $ **if and only if** $ p_i > p_j $.\n- Each knight can kill **at most $ k $** other knights.\n- Upon killing knight $ j $, knight $ i $ acquires all coins $ c_j $.\n- Knights cannot kill themselves.\n- The goal is to compute, for each knight $ i $, the **maximum total coins** knight $ i $ can accumulate by killing at most $ k $ other knights with strictly smaller power.\n\n**Objective:**\n\nFor each knight $ i \\in \\{1, 2, \\dots, n\\} $, compute:\n\n$$\n\\max \\left\\{ c_i + \\sum_{j \\in S} c_j \\ \\middle|\\ S \\subseteq \\{ j \\mid p_j < p_i \\},\\ |S| \\leq k \\right\\}\n$$\n\nThat is, for each knight $ i $, maximize the sum of their own coins plus the coins of up to $ k $ knights with strictly smaller power.\n\n**Note:** Since powers are distinct, we can sort knights by power. For each knight $ i $, consider only knights with lower power, and select up to $ k $ among them with the **maximum coins** (greedy selection).\n\n**Output:**\n\nA sequence of $ n $ integers, where the $ i $-th integer is the maximum coins knight $ i $ can have under the above rules.","simple_statement":null,"has_page_source":false}