配点 : 600 点
問題文
长度 N 整数序列 A,B 。
頂点 u 和顶点 连接 v 的边的权重为 完整的图表是 A_u\times A_v + B_u \times B_v 求 G 的最小生成树的权重。 连接
制約
- 2 \leq N \leq 5\times 10^4
- |A_i|, |B_i| \le 10^6
- 所有输入均为整数
入力
输入将以以下形式从标准输入给出。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
打印答案。 请创建一个输出
入力例 1
3 1 3 -1 -2 0 -4
出力例 1
0
頂点 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
4 1 1 -1 -1 1 1 -1 -1
出力例 2
-6
(A_i, B_i) = (A_j, B_j) 变为 i, j (i \neq j) 也可能存在。 给出
入力例 3
10 -593389 -914534 -534565 -257272 -723595 763395 -272810 -869922 449729 -111959 743146 -30912 -528945 903153 -162840 -807868 227877 -433864 751438 34288
出力例 3
-5395522482698