交换权柄

G-14数据枢纽的最深处，有一扇由两个相邻节点控制的门。节点A和节点B——它们控制着门的开闭权限。但Zero设置了一个陷阱：只有当一个节点的"影响值"乘以另一个节点的"防御值"的排列顺序最小时，门才会打开。

"这就是相邻博弈。"Echo站在两个节点中间，投影被它们的红蓝光切割成两半，"两个节点，两种排列——A在前B在后，或者B在前A在后。我们要找到让总代价最小的顺序。"

"总代价是啥子？"CC问。

"前一个节点的影响值乘以后一个节点的防御值。"你说，"如果A在前，代价是A的影响 × B的防御；如果B在前，代价是B的影响 × A的防御。"

"那就直接比。"CC说，"两种都算一下，选小的。"

"但这里不止两个节点。"Echo调出完整的权限链——十几个节点排成一排，每个都有影响值和防御值，"整个序列的顺序决定了总代价。要找到全局最优的顺序。"

你开始推导。假设相邻的两个节点i和j，i在前j在后的代价是 $a_i \times b_j$，j在前i在后的代价是 $a_j \times b_i$。如果i在前更优，那么 $a_i \times b_j < a_j \times b_i$，也就是 $a_i / b_i < a_j / b_j$。

"按影响值除以防御值排序。"你说，"比值小的放前面。然后一对一对检查——如果当前顺序里有一对相邻节点不满足这个规矩，交换它们会让总代价变小。不断交换，直到没有遗憾。"

"就像冒泡。"CC说，"把大的泡到后面，小的沉到前面。"

"对。"

你把十几个节点按比值排序，然后依次输入门上的验证接口。最后一个节点输入后，门发出一声低沉的轰鸣，像是一个古老的机关被唤醒。

"开了。"Echo说。

CC把数据刀插回腰间："里面就是G-14的核心？"

"不。"Echo说，"里面是一条通道——通往下一层防线的通道。"

题目描述

$n$ 个节点，每个节点有影响力 $a_i$ 和防御力 $b_i$。将它们排成一排，最小化相邻节点之间 $a_i \times b_j$ 的总和。

输入格式

$n$。然后 $n$ 行，每行 $a_i, b_i$。

输出格式

最小总代价。

输入样例

3
1 1
2 3
7 4
4 6

输出样例

2

提示

• 按 $a_i / b_i$ 从小到大排序。
• 用相邻交换证明：若 $a_i / b_i < a_j / b_j$，则 $i$ 应在 $j$ 前面。
• 排序后依次计算相邻乘积之和。

快速决策

六个碎片，六条裂隙，一棵星树，十二只鹰眼，五个时段，一串权柄。

G-14数据枢纽的外围防线被逐个击破。Echo站在通道入口，投影比以往任何时候都更明亮。

"下一层。"她说，"是基本算法实战。"

"又是实战？"CC问。

"对。"Echo说，"这次不是单一策略——是多种算法的组合。迷宫、信标、暗影、机群、面板、富矿、物资、奇点。八个关卡，八个考验。"

[下一章：基本算法实战 —— G-14核心]