题目内容

二维平面上分布着 $m$ 个居民区。第 $i$ 个居民区的坐标为 $(a_i, b_i)$，居民人数为 $w_i$。

现在需要在该平面上为一座工厂选定一个落点 $(P, Q)$。工厂落点可以在二维平面上任意选取。居民从住处到工厂的路程按曼哈顿距离计算：对于任意两个坐标 $(s, t)$ 与 $(u, v)$，它们之间的曼哈顿距离为 $|s - u| + |t - v|$。

因此，第 $i$ 个居民区到工厂 $(P, Q)$ 的加权曼哈顿距离定义为：

目标是选择工厂落点 $(P, Q)$，使所有居民区的加权曼哈顿距离之和尽可能小。请输出这个最小值。

约束条件

• 居民区数量 $m$ 在 1 到 10000 之间。
• 每个居民区的坐标 $a_i$ 和 $b_i$ 的绝对值均不超过 10^9。
• 每个居民区的人数 $w_i$ 在 1 到 10^6 之间。

输入描述

第一行包含一个整数 $m$，表示居民区的数量。

接下来 $m$ 行，每行包含三个整数 $a_i$、$b_i$、$w_i$，分别表示第 $i$ 个居民区的横坐标、纵坐标和居民人数。

输出描述

输出一个整数，表示所有居民区到工厂的最小加权曼哈顿距离之和。

样例1

输入

1
0 0 5

输出

0

说明

只有 1 个居民区，坐标为 $(0,0)$，人数为 5。工厂可以直接选在该居民区位置 $(0,0)$。

此时加权曼哈顿距离为 $5 \times (|0-0|+|0-0|)=0$，所以最小值为 0。

样例2

输入

3
-10 0 1
0 0 2
10 0 1

输出

20

说明

有 3 个居民区，横坐标分别为 $-10$、$0$、$10$，人数分别为 $1$、$2$、$1$，总人数为 4。

按人数加权寻找横坐标中位数：累计人数第一次达到总人数一半 2 时，对应的横坐标为 $0$。所有纵坐标都是 $0$，因此纵坐标中位数也是 $0$。工厂选在 $(0,0)$。

加权曼哈顿距离之和为：

$1 \times |-10-0| + 2 \times |0-0| + 1 \times |10-0| = 10+0+10=20$

所以输出 20。

样例3

输入

4
0 0 3
2 0 2
0 2 1
2 2 4

输出

18

说明

有 4 个居民区，总人数为 10。

先看横坐标：按横坐标排序后累加人数，当累计人数第一次达到总人数一半 5 时，对应的横坐标为 $2$，因此工厂横坐标 $P=2$。

再看纵坐标：纵坐标为 $0$ 的居民区人数之和为 $3+2=5$，已经达到总人数一半 5，因此工厂纵坐标 $Q=0$。

工厂选在 $(2,0)$。各居民区的加权曼哈顿距离分别为：

$(0,0)$ 人数 $3$：$3 \times (|0-2|+|0-0|)=6$

$(2,0)$ 人数 $2$：$2 \times (|2-2|+|0-0|)=0$

$(0,2)$ 人数 $1$：$1 \times (|0-2|+|2-0|)=4$

$(2,2)$ 人数 $4$：$4 \times (|2-2|+|2-0|)=8$

总和为 $6+0+4+8=18$，所以输出 18。