LIS

Problem Description

给定长度为 $n$ 的排列 $a$，删除 $a_i$ 的代价是 $b_i$。 现在希望删除一些 $a_i$，使得删完后 $a$ 的 LIS（最长上升子序列）长度 $\le k$，最小化被删除元素的代价和。 对 $1 \le k \le n$ 分别求出答案。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le5$），表示测试数据组数。 对于每组数据，第一行一个整数 $n$（$1 \le n \le 500$）。 第二行 $n$ 个整数 $a_1 \sim a_n$（$1 \le a_i \le n$，$a_i$ 互不相同）。 第三行 $n$ 个整数 $b_1 \sim b_n$（$1 \le b_i \le 10^6$）。

Output

对于每组数据，输出一行 $n$ 个整数，第 $i$ 个整数表示 $k=i$ 时的最小代价和。

Sample Input

4
5
3 1 4 2 5
6 7 10 2 4
6
2 1 5 6 4 3
8 7 9 7 5 10
6
1 3 2 5 6 4
2 10 2 10 8 2
5
1 2 3 4 5
5 4 3 2 1

Sample Output

16 4 0 0 0
22 7 0 0 0 0
22 10 2 0 0 0
10 6 3 1 0

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）