题目内容

现在要在二维平面上选定一个工厂落点 $(P, Q)$，目标是让所有居民走到工厂的加权曼哈顿距离之和尽可能小。请输出这个最小值。

该地区共有 $m$ 个居民区。第 $i$ 个居民区位于 $(a_i, b_i)$，住有 $w_i$ 名居民。

两点之间的路程按曼哈顿距离计算：$(s, t)$ 到 $(u, v)$ 为 $|s-u|+|t-v|$。第 $i$ 个居民区对工厂的加权曼哈顿距离为

解答要求：

• 时间限制：C/C++ $100$ms，其他语言：$200$ms
• 内存限制：C/C++ $256$MB，其他语言：$512$MB

输入描述

第一行一个整数 $m$（$1 \le m \le 10000$），表示居民区个数。

接下来 $m$ 行，每行三个整数 $a_i$、$b_i$、$w_i$（$-10^9 \le a_i, b_i \le 10^9$，$1 \le w_i \le 10^6$），表示第 $i$ 个居民区的坐标和居民人数。

输出描述

输出一个整数，表示最小的加权曼哈顿距离之和。

样例1

输入

3
0 3 2
5 3 4
5 7 1

输出

14

说明

把工厂建在 $(5, 3)$ 时：

• 到 $(0, 3)$ 的距离是 $|0-5|+|3-3|=5$，人数 $2$，贡献 $5 \times 2 = 10$
• 到 $(5, 3)$ 的距离是 $0$，人数 $4$，贡献 $0$
• 到 $(5, 7)$ 的距离是 $|5-5|+|7-3|=4$，人数 $1$，贡献 $4$
• 总和为 $10+0+4=14$，这就是最小的加权曼哈顿距离之和

样例2

输入

3
0 1 1
4 1 1
2 6 1

输出

9

说明

把工厂建在 $(2, 1)$ 时：

• 到 $(0, 1)$ 的距离是 $2$，贡献 $2$
• 到 $(4, 1)$ 的距离是 $2$，贡献 $2$
• 到 $(2, 6)$ 的距离是 $5$，贡献 $5$
• 总和为 $2+2+5=9$，这就是最小的加权曼哈顿距离之和