题目描述

作为一名真正的邪恶科学家，你已经熟练掌握了制造越来越巨大、越来越可怕的果冻的方法。

实验室中央的一张圆桌上摆放着 $N$ 个矩形果冻，它们构成一个环形数组。也就是说，除了通常意义下相邻的果冻外，第一个果冻与最后一个果冻也互相相邻。

每个果冻由两个正整数描述：高度和宽度。

任意时刻，你可以选择两个相邻的果冻，将它们合并为一个新果冻。新果冻的：

• 高度等于两个原果冻高度的较大值；
• 宽度等于两个原果冻宽度的较大值。

新果冻占据原来两个果冻的位置，圆桌上的果冻数量减少 $1$。之后，它也可以继续与相邻果冻合并。

高度为 $h$、宽度为 $w$ 的果冻面积为 $h\cdot w$。

你可以执行任意次合并，也可以一次都不合并。请最大化最终剩余果冻的面积之和。

实现要求

你需要实现函数：

long long solve(std::vector<int> H,
                std::vector<int> W);

其中：

• H 和 W 的长度均为 $N$；
• $H_i$ 和 $W_i$ 分别表示第 $i$ 个果冻的高度和宽度；
• 果冻按照它们在圆桌上的环形顺序给出；
• 函数应返回经过任意次合并后，可以得到的最大面积总和。

数据范围

• $1\le N\le 3\cdot 10^5$；
• $1\le H_i,W_i\le 10^6$。

答案可能超过 32 位有符号整数范围。

子任务

样例

样例 1

输入：
2
6 3
2 7

输出：
42

不合并时总面积为：

合并后得到一个 $6\times 7$ 的果冻，面积为 $42$。

样例 2

输入：
4
1 5
10 10
5 1
6 7

输出：
152

样例 3

输入：
5
6 2
5 1
1 5
2 7
1 2

输出：
67

一种最优方案是把环分成两段：

• 果冻 $4,5,1$ 合并，得到 $6\times 7$，面积为 $42$；
• 果冻 $2,3$ 合并，得到 $5\times 5$，面积为 $25$。

总面积为 $42+25=67$。

样例 4

输入：
1
380385 222650

输出：
84692720250

只有一个果冻，答案就是：

本地评测器格式

本地评测器读取：

N
H1 W1
H2 W2
...
HN WN

并输出 solve 的返回值。