AT_pakencamp_2023_day1_p MST (Hard)

给定长度为 $N$ 的整数序列 $A, B$。 构建一个完全图 $G$，其顶点 $u$ 和顶点 $v$ 之间的边权为 $A_u \times A_v + B_u \times B_v$。请你求出这个完全图的最小生成树的权值。

输入将以如下格式从标准输入给出。 > $N\ A_1\ A_2\ \ldots\ A_N\ B_1\ B_2\ \ldots\ B_N$

请输出答案。

### 样例解释 1 顶点 $1$ 和顶点 $2$ 之间的边权为 $1 \times 3 + (-2) \times 0 = 3$， 顶点 $1$ 和顶点 $3$ 之间的边权为 $1 \times (-1) + (-2) \times (-4) = 7$， 顶点 $2$ 和顶点 $3$ 之间的边权为 $3 \times (-1) + 0 \times (-4) = -3$。 因此，选取连接 $1$ 与 $2$ 的边，以及 $2$ 与 $3$ 的边，可以构成最小生成树，其权值为 $0$。 ### 样例解释 2 可能存在 $i, j$ 满足 $(A_i, B_i) = (A_j, B_j)$ 且 $i \neq j$。 ### 数据范围 - $2 \leq N \leq 5 \times 10^4$ - $|A_i|, |B_i| \le 10^6$ - 输入均为整数。 由 ChatGPT 5 翻译