P15884 [ICPC 2026 NAC] Jelly Fusion

作为一位邪恶科学家，你已经掌握了如何在秘密实验室中制造更大、更恐怖的果冻怪。在你的圆形实验台周围，摆放着一个由 $N$ 个矩形果冻组成的 **环形数组**，每个果冻都有一定的高度和宽度。注意，第一个果冻和最后一个果冻是相邻的。 你可以将两个相邻的父果冻融合在一起，生成一个新的组合果冻，其高度等于两个父果冻高度的最大值，宽度等于两个父果冻宽度的最大值。融合后的果冻会替换掉原来两个父果冻在环形数组中的位置（此时数组长度减少 1），并且原则上它可以继续与它相邻的两个果冻之一再次融合。 你可以进行任意次数的融合操作，目的是最大化所有果冻的面积之和。毕竟，你的果冻能覆盖的总面积越大，你能征服的城市就越多！

输入的第一行包含一个整数 $N$ $(1 \leq N \leq 3\cdot 10^5)$，表示实验台上初始的果冻数量。 接下来的 $N$ 行按顺序描述这些果冻。第 $i$ 行包含两个空格分隔的整数 $h_i$ 和 $w_i$ $(1 \leq h_i, w_i \leq 10^6)$，表示第 $i$ 个果冻的高度和宽度。

输出一个整数：在任意次融合操作后，环形数组中剩余的果冻的面积之和的最大可能值。

翻译由 DeepSeek V3.2 完成