AT_ndpc2026_f 集合

You are given a permutation $ P = (P_1, P_2, \dots, P_N) $ of $ (1, 2, \dots, N) $ and an integer array $ A_1, A_2, \dots, A_N $ of length $ N $ . A subset $ S $ of the set $ \lbrace 1,2,\dots,N \rbrace $ is called a **good set** if it satisfies the following condition: - For every pair of integers $ (x, y) $ such that $ x < y $ and $ x, y \in S $ , the following holds: - Let $ z $ be the integer such that $ P_z = \min(P_x, P_{x+1}, \dots, P_y) $ . (Such a $ z $ is uniquely determined.) Then, it must hold that $ z \in S $ . The **cost** of a good set $ S $ is defined as $ \displaystyle \sum_{i \in S} A_i $ . For each $ K = 1, 2, \dots, N $ , find the minimum possible cost among all good sets of size $ K $ . You are given $ T $ test cases. Solve each of them.

The input is given from standard input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Print $ T $ lines. For the $ i $ -th line, output the answer for the $ i $ -th test case. For each test case, output the answers for $ K = 1,2,\dots,N $ in one line, separated by spaces.

### Sample Explanation 1 In the first test case: - For $ K=1 $ , $ S=\lbrace 1 \rbrace $ is optimal, - For $ K=2 $ , $ S=\lbrace 3,4 \rbrace $ is optimal, - For $ K=3 $ , $ S=\lbrace 1,2,3 \rbrace $ is optimal, - For $ K=4 $ , $ S=\lbrace 1,2,3,4 \rbrace $ is optimal. ### Constraints - $ 1 \leq T \leq 5000 $ - $ 1 \leq N \leq 5000 $ - $ 1 \leq A_i \leq 10^9 $ - $ (P_1, P_2, \dots, P_N) $ is a permutation of $ (1,2,\dots,N) $ - The sum of $ N $ over all test cases is at most $ 5000 $ - All input values are integers