题目内容

某大学计划在校园内的指定矩形区域内新建一个快递站。该矩形区域的范围是横坐标 $X_L$ 到 $X_R$、纵坐标 $Y_L$ 到 $Y_R$，也就是说快递站建址 $(P, Q)$ 必须满足 $X_L \le P \le X_R$ 且 $Y_L \le Q \le Y_R$。

校园里有 $n$ 栋宿舍楼。第 $i$ 栋楼的位置为 $(x_i, y_i)$，每天有 $w_i$ 件快递需要取。所有学生都要沿校园道路走到快递站，路程按曼哈顿距离计算：从 $(s, t)$ 到 $(u, v)$ 的曼哈顿距离为 $|s-u|+|t-v|$。第 $i$ 栋楼对总路程的贡献是

对于一维数轴上的若干点，使到所有点的加权绝对距离之和最小的位置是它们的加权中位数。

请你在这个矩形区域内选择一个建址 $(P, Q)$，使所有宿舍楼的贡献之和最小，并输出这个最小值。

输入描述

第一行一个整数 $n$（$1 \le n \le 10^5$），表示宿舍楼个数。

接下来 $n$ 行，每行三个整数 $x_i$、$y_i$、$w_i$（$-10^9 \le x_i, y_i \le 10^9$，$1 \le w_i \le 10^6$），表示第 $i$ 栋宿舍楼的位置和每日快递件数。

最后一行四个整数 $X_L$、$X_R$、$Y_L$、$Y_R$（$-10^9 \le X_L \le X_R \le 10^9$，$-10^9 \le Y_L \le Y_R \le 10^9$），表示矩形区域的范围。

输出描述

输出一个整数，表示最小的总加权曼哈顿距离之和。题目保证答案能用 $64$ 位有符号整数表示。

数据范围

• $1 \le n \le 10^5$
• $-10^9 \le x_i, y_i \le 10^9$，$1 \le w_i \le 10^6$
• $-10^9 \le X_L \le X_R \le 10^9$，$-10^9 \le Y_L \le Y_R \le 10^9$

分档：

• 对于 $40\%$ 的数据：$n \le 100$
• 对于 $70\%$ 的数据：$n \le 5000$
• 对于 $100\%$ 的数据：$n \le 10^5$

样例1

输入

3
2 5 3
8 5 5
8 1 2
-100 100 -100 100

输出

26

说明

矩形范围 $[-100,100]\times[-100,100]$ 很大，最优点不受约束影响。

把快递站建在 $(8, 5)$ 时：

• 到 $(2, 5)$ 的距离是 $|2-8|+|5-5|=6$，快递数 $3$，贡献 $6\times 3 = 18$
• 到 $(8, 5)$ 的距离是 $0$，快递数 $5$，贡献 $0$
• 到 $(8, 1)$ 的距离是 $|8-8|+|1-5|=4$，快递数 $2$，贡献 $4\times 2 = 8$

总和 $= 18+0+8 = 26$，这就是最小的总加权曼哈顿距离之和。

样例2

输入

2
0 0 5
10 0 5
6 8 -100 100

输出

50

说明

横坐标方向宿舍楼位置为 $0$（权重 $5$）和 $10$（权重 $5$），总权重 $10$，前缀权重第一次 $\ge 5$ 时对应位置 $0$，所以无约束时最优横坐标 $P^*=0$。但 $P^*=0$ 不在 $[X_L,X_R]=[6,8]$ 内，需要把最优点夹到矩形的左边界，取 $P=X_L=6$。

纵坐标方向两组都在 $0$，$Q=0$（无约束影响）。

把快递站建在 $(6, 0)$ 时：

• 到 $(0, 0)$ 的距离是 $|0-6|+|0-0|=6$，快递数 $5$，贡献 $30$
• 到 $(10, 0)$ 的距离是 $|10-6|+|0-0|=4$，快递数 $5$，贡献 $20$

总和 $= 30+20 = 50$，这就是最小的总加权曼哈顿距离之和。

样例3

输入

3
5 0 1
5 15 1
5 30 1
0 100 0 12

输出

33

说明

横坐标方向三栋楼都在 $5$，$P=5$（无约束影响）。

纵坐标方向宿舍楼位置为 $0$、$15$、$30$，各权重 $1$，总权重 $3$，前缀权重第一次 $\ge 1.5$ 时对应位置 $15$，所以无约束时最优纵坐标 $Q^*=15$。但 $Q^*=15$ 不在 $[Y_L,Y_R]=[0,12]$ 内，需要把最优点夹到矩形的右边界，取 $Q=Y_R=12$。

把快递站建在 $(5, 12)$ 时：

• 到 $(5, 0)$ 的距离是 $|5-5|+|0-12|=12$，快递数 $1$，贡献 $12$
• 到 $(5, 15)$ 的距离是 $|5-5|+|15-12|=3$，快递数 $1$，贡献 $3$
• 到 $(5, 30)$ 的距离是 $|5-5|+|30-12|=18$，快递数 $1$，贡献 $18$

总和 $= 12+3+18 = 33$，这就是最小的总加权曼哈顿距离之和。

样例4

输入

1
100 200 7
-1000 1000 -1000 1000

输出

0

说明

只有一栋宿舍楼。把快递站建在该楼位置 $(100, 200)$，无论权重多大，总加权曼哈顿距离都是 $7 \times 0 = 0$。该位置也在矩形区域内，所以最优总距离为 $0$。