点对之和(Pair Sum)

题目描述

数轴上有 $N$ 个点，其中第 $i$ 个点的坐标为 $X_i$，每个点还带有一个权值，记为 $W_i$。任意两个点 $i$ 与 $j$ 之间的作用效应记为它们权值的最大值与它们距离的积，也就是 $\max(W_i,W_j)\cdot |X_i-X_j|$。请求出数轴上所有点对的作用效应之和。

输入格式

• 第一行：单个整数表示 $N$；
• 第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数分别表示 $X_i$ 与 $W_i$。

输出格式

• 单个整数：表示所有点对两两之间的作用效应之和。

样例输入 #1

3
-2 100
3 1000
1 10

样例输出 #1

7300

说明：$|-2-3|\times1000+|-2-1|\times100+|3-1|\times1000=7300$

数据范围

• 对于 $30\%$ 的数据，$1\leq N\leq 1000$；
• 对于 $60\%$ 的数据，$1\leq N\leq 50,000$；
• 对于 $100\%$ 的数据，$1\leq N\leq 100,000$，$-1,000,000\leq X_i,W_i\leq 1,000,000$。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布