分数: 500 点
问题陈述
新的 AtCoder City 有无限的街道网格,如下:
- 在城市的中心矗立着一座钟楼。 (0, 0) 是该点的坐标。
- 一条笔直的街道,我们称之为 东西大街,东西走向并经过钟楼。 x- 二维坐标平面中的轴。
- 还有无数条与东西大街平行的街道,距离为 1 他们之间。它们对应于线 二维坐标平面中的 \ldots, y = -2, y = -1, y = 1, y = 2, \ldots 。
- 一条笔直的街道,我们称之为 南北大街,南北走向,经过钟楼。 y- 二维坐标平面中的轴。
- 还有无数条与南北大街平行的街道,距离为 1 他们之间。它们对应于线 二维坐标平面中的 \ldots, x = -2, x = -1, x = 1, x = 2, \ldots 。
有 N AtCoder 新城住宅区。 i第一个区域位于与坐标的交点处 (X_i, Y_i) 人口为 P_i。城市中的每个公民都居住在这些区域之一。
该市目前只有两条铁路,无限延伸,一条沿东西大街,另一条沿南北大街。
市长M-kun认为这些对于通勤者来说不够,所以他决定选择 K 街道并沿着每条街道建造一条无限延伸的铁路。
让 步行距离
每个公民的 是他/她的居住区到最近的铁路的距离。
M君想要修建铁路,以便所有公民的步行距离总和, S被最小化。
对于每个 K = 0, 1, 2, \dots, N,最小可能值是多少 S 修建铁路后?
约束
- 1 \leq N \leq 15
- -10 \ 000 \leq X_i \leq 10 \ 000
- -10 \ 000 \leq Y_i \leq 10 \ 000
- 1 \leq P_i \leq 1 \ 000 \ 000
- 的位置 N 住宅区, (X_i, Y_i),都是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 P_1 X_2 Y_2 P_2 : : : X_N Y_N P_N
输出
打印答案 N+1 行。
的
树的 i第行 (i = 1, \ldots, N+1) 应包含最小可能值 S 为该案修建铁路后 K = i-1.
示例输入 1
3 1 2 300 3 3 600 1 4 800
示例输出 1
2900 900 0 0
当 K = 0, 辖区居民 1, 2,和 3 必须步行的距离 1, 3,和 1分别到达铁路。
因此,所有公民的步行距离总和, S是 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900.
当 K = 1,如果我们沿着该线对应的街道修建一条铁路 y = 4 在坐标平面上,区域居民的步行距离 1, 2,和 3 成为 1, 1,和 0。
然后, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900.
对于修建铁路的地点,我们有许多其他选择,但没有一个能够使 S 小于 900.
当 K = 2,如果我们沿着对应线路的街道修建一条铁路 x = 1 和 x = 3 在坐标平面上,所有公民步行距离可达一条铁路 0,所以 S = 0。我们还可以有 S = 0 当 K = 3.
下图展示了该案例中修建铁路的最佳方式 K = 0, 1, 2.
涂成蓝色的街道代表我们修建铁路的道路。

示例输入 2
5 3 5 400 5 3 700 5 5 1000 5 7 700 7 5 400
示例输出 2
13800 1600 0 0 0 0
下图展示了该案例中修建铁路的最佳方式 K = 1, 2.

示例输入 3
6 2 5 1000 5 2 1100 5 5 1700 -2 -5 900 -5 -2 600 -5 -5 2200
示例输出 3
26700 13900 3200 1200 0 0 0
下图展示了该案例的最佳铁路建设方式 K = 3.

示例输入 4
8 2 2 286017 3 1 262355 2 -2 213815 1 -3 224435 -2 -2 136860 -3 -1 239338 -2 2 217647 -1 3 141903
示例输出 4
2576709 1569381 868031 605676 366338 141903 0 0 0
下图展示了该案例的最佳铁路建设方式 K = 4.
