Traveling Salescat
Contest: Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Difficulty rating: 2900
Tags: constructive algorithms, dp, geometry, graphs, greedy, math, sortings

You are a cat selling fun algorithm problems. Today, you want to recommend your fun algorithm problems to $$$k$$$ cities.

There are a total of $$$n$$$ cities, each with two parameters $$$a_i$$$ and $$$b_i$$$. Between any two cities $$$i,j$$$ ($$$i\ne j$$$), there is a bidirectional road with a length of $$$\max(a_i + b_j , b_i + a_j)$$$. The cost of a path is defined as the total length of roads between every two adjacent cities along the path.

For $$$k=2,3,\ldots,n$$$, find the minimum cost among all simple paths containing exactly $$$k$$$ distinct cities.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1500$$$) — the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 3\cdot 10^3$$$) — the number of cities.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains two integers $$$a_i,b_i$$$ ($$$0 \leq a_i,b_i \leq 10^9$$$) — the parameters of city $$$i$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$9\cdot 10^6$$$.

Output format:
For each test case, print $$$n-1$$$ integers in one line. The $$$i$$$-th integer represents the minimum cost when $$$k=i+1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case:

- For $$$k=2$$$, the optimal path is $$$1\to 2$$$ with a cost of $$$\max(0+1,2+2)=4$$$.
- For $$$k=3$$$, the optimal path is $$$2\to 1\to 3$$$ with a cost of $$$\max(0+1,2+2)+\max(0+3,3+2)=4+5=9$$$.

In the second test case:

- For $$$k=2$$$, the optimal path is $$$1\to 4$$$.
- For $$$k=3$$$, the optimal path is $$$2\to 3\to 5$$$.
- For $$$k=4$$$, the optimal path is $$$4\to 1\to 3\to 5$$$.
- For $$$k=5$$$, the optimal path is $$$5\to 2\to 3\to 1\to 4$$$.

Example input:
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

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

Editorial:
Let $$$x_i = \frac{a_i + b_i}{2}$$$, $$$y_i = \frac{a_i - b_i}{2}$$$. Then $$$\max(a_i + b_j , b_i + a_j) = \max( x_i + y_i + x_j - y_j , x_i - y_i + x_j + y_j) = x_i + x_j + \max(y_i - y_j, y_j - y_i)$$$
$$$ = x_i + x_j + |y_i - y_j|$$$.
Consider a road that passes through $$$k$$$ different cities, and consider the contribution as two parts, $$$x$$$ and $$$y$$$. For the contribution of $$$x$$$, the first and last cities will only contribute to the answer once. And all other cities on the path will contribute twice.
For the contribution of $$$y$$$, after determining the cities that need to be passed through and the two cities as starting or ending cities (referred to as endpoint cities), you can start from the endpoint city with smaller $$$y$$$, move to the city with the smallest $$$y$$$ among the cities to be passed through, then move to the city with the largest $$$y$$$ among the cities to be passed through, and finally move to the endpoint city with larger $$$y$$$. This way, the minimum contribution of y can be obtained while passing through all the cities that need to be passed through.
You can sort the cities by $$$y$$$ and perform a dp to find the minimum answer among the first $$$i$$$ cities where $$$j$$$ cities have been selected, including $$$0$$$ or $$$1$$$ or $$$2$$$ endpoint cities. The total time complexity is $$$O(n^2)$$$.