AT_ndpc2026_f 集合

$ (1, 2, \dots, N) $ の順列 $ P = (P_1, P_2, \dots, P_N) $ および長さ $ N $ の整数列 $ A_1, A_2, \dots, A_N $ が与えられます。 整数集合 $ \lbrace 1,2,\dots, N \rbrace $ の部分集合 $ S $ であって以下の条件を満たすものを **良い集合** と呼びます。 - $ x \lt y $ かつ $ x, y \in S $ である整数の組 $ (x, y) $ 全てに対して以下の条件が成り立つ。 - $ z $ を $ P_z = \min(P_x, P_{x+1}, \dots, P_y) $ を満たす整数とする。(このような $ z $ は一意に定まる。) この時、 $ z \in S $ が成り立つ。 良い集合 $ S $ の **コスト** を $ \displaystyle \sum_{i \in S} A_i $ として定義します。 $ K = 1, 2, \dots, N $ について、サイズ $ K $ の良い集合のコストとしてあり得る値の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。 各テストケースでは、 $ K=1,2,\dots,N $ に対する答えを空白区切りで $ 1 $ 行に出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースでは、 - $ K=1 $ の時は $ S=\lbrace 1 \rbrace $ が、 - $ K=2 $ の時は $ S=\lbrace 3,4 \rbrace $ が、 - $ K=3 $ の時は $ S=\lbrace 1,2,3 \rbrace $ が、 - $ K=4 $ の時は $ S=\lbrace 1,2,3,4 \rbrace $ が良い集合の中でコスト最小です。 ### 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) $ は $ (1,2,\dots,N) $ の順列 - 全てのテストケースに対する $ N $ の総和は $ 5000 $ 以下 - 入力される値は全て整数