CF2062F.Traveling Salescat

你是一位售卖趣味算法题的猫咪。今天，你打算向 $k$ 个城市推荐你的趣味算法题。

总共有 $n$ 个城市，每个城市有两个参数 $a_i$ 和 $b_i$。在任意两个城市 $i,j$（$i\ne j$）之间，有一条双向道路，其长度为 $\max(a_i + b_j , b_i + a_j)$。一条路径的成本定义为路径上每两个相邻城市之间道路长度的总和。

对于 $k=2,3,\ldots,n$，找出包含恰好 $k$ 个不同城市的简单路径中的最小成本。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1500$）—— 表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 3\cdot 10^3$）—— 表示城市的数量。

接下来是 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$（$0 \leq a_i,b_i \leq 10^9$）—— 表示城市 $i$ 的参数。

保证 $\sum n^2 \leq 9 \times 10^6$。

对于每个测试用例，在一行中输出 $n-1$ 个整数。第 $i$ 个整数表示当 $k=i+1$ 时的最小成本。

在第一个测试用例中：

• 当 $k=2$ 时，最优路径为 $1\to 2$，其成本为 $\max(0+1,2+2)=4$。
• 当 $k=3$ 时，最优路径为 $2\to 1\to 3$，其成本为 $\max(0+1,2+2)+\max(0+3,3+2)=4+5=9$。

在第二个测试用例中：

• 当 $k=2$ 时，最优路径为 $1\to 4$。
• 当 $k=3$ 时，最优路径为 $2\to 3\to 5$。
• 当 $k=4$ 时，最优路径为 $4\to 1\to 3\to 5$。
• 当 $k=5$ 时，最优路径为 $5\to 2\to 3\to 1\to 4$。