题目描述

F. 旅行售卖猫
每个测试点时间限制：$2$ 秒
每个测试点内存限制：$512$ 兆字节

你是一只售卖有趣算法题的猫。今天，你想把你的有趣算法题推荐给 $k$ 个城市。

一共有 $n$ 个城市，每个城市有两个参数 $a_i$ 和 $b_i$。对于任意两个不同的城市 $i, j$（$i \ne j$），它们之间有一条双向道路，道路长度为 $\max(a_i + b_j,\; b_i + a_j)$。一条路径的代价定义为路径上相邻城市之间道路长度的总和。

对于 $k = 2, 3, \dots, n$，求出所有恰好包含 $k$ 个不同城市的简单路径中的最小代价。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 1500$）—— 测试用例的数量。
对于每个测试用例，第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^3$）—— 城市的数量。
接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i, b_i$（$0 \le a_i, b_i \le 10^9$）—— 城市 $i$ 的参数。
保证所有测试用例的 $n^2$ 之和不超过 $9 \cdot 10^6$。

输出格式

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

3
3
0 2
2 1
3 3
5
2 7
7 5
6 3
1 8
7 5
8
899167687 609615846
851467150 45726720
931502759 23784096
918190644 196992738
142090421 475722765
409556751 726971942
513558832 998277529
294328304 434714258

4 9
10 22 34 46
770051069 1655330585 2931719265 3918741472 5033924854 6425541981 7934325514

说明
在第一个测试用例中：

• 当 $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$。