题目描述

扬非常喜欢玩电子游戏。去年夏天，他一直在玩游戏《Pac-Man 2: Back on Track》。游戏内存中记录着一个一维棋盘，共有 N 个格子。

每个格子 i 中都有 1 颗樱桃，它的重量为 w_i。扬想知道：如果对每一个关卡都采用最优策略，那么他总共最多能得到多少分。

在每个关卡开始时，会选定一对整数 (l, r)，满足 l ≤ r，它们是该关卡的左右端点。之后，只有这两个端点之间的格子仍然处于激活状态。

扬在每个关卡开始时的分数为 0。设某一步当前激活的格子为：

$$a_l, a_{l+1}, \dots, a_r$$

则会发生如下过程：

• 如果当前没有激活格子，则游戏结束，扬输掉该关卡，他的最终得分就是当前已经获得的分数；
• 否则，游戏会在当前区间中找到最重的樱桃，设它所在的位置为 p；
• 扬按下左键 L 或右键 R，并将自己的得分加 1；
  • 如果按下左键，则新的激活格子变为

$$a_l, a_{l+1}, \dots, a_{p-1}$$

• 如果按下右键，则新的激活格子变为

$$a_{p+1}, a_{p+2}, \dots, a_r$$

• 然后游戏在新的激活格子集合上重复上述过程。

由于制造缺陷，并不是所有关卡都可以开始。只有某些格子是完好的，它们才能被选作一个关卡的起点或终点。

形式化地，给定一个大小为 M 的集合 S，表示可作为区间端点的位置。一个区间只有在其两个端点都属于 S 时，才能作为游戏起始区间。

可以证明，关卡总数为：

$$\frac{M(M+1)}{2}$$

请帮助扬求出：若他把每个可能的关卡都以最优方式玩一遍，那么他总共能得到多少分。

实现细节

你需要实现如下函数：

long long solve(const std::vector<int>& w, const std::vector<int>& S);

该函数只会被评测程序调用一次。参数 w 表示樱桃重量数组，参数 S 表示可作为区间端点的位置集合。函数需要返回所有关卡的最优分数之和。

你的程序文件应命名为 pacman.cpp。它可以包含你所需的其他代码和函数，但不能包含主函数 main。同时，你不能从标准输入读入，也不能向标准输出输出。

程序必须通过预处理指令包含头文件：

#include "pacman.h"

限制

• 1 ≤ N, M ≤ 500000
• w_1, w_2, ..., w_N 是 1 到 N 的一个排列
• 对于 i ≠ j，有 S_i ≠ S_j

子任务

子任务	分值	N	M	其他限制
1	0	-		样例测试
2	5	≤ 100		-
6		≤ 500000	≤ 10
4	10	≤ 1000
5	15	≤ 5000
6	30	≤ 500000	≤ 1000
7	35		≤ 500000

某个子任务的分数只有在该子任务下的所有测试都通过时才能获得。

注：上表中的子任务编号按原 PDF 题面原样保留；原题面中该编号处存在明显的排版/编号异常。

示例

输入

4 3
1 4 2 3
1 2 4

输出

11

说明

可以作为游戏起始区间的有：(1, 1)、(2, 2)、(4, 4)、(1, 2)、(1, 4) 和 (2, 4)。

考虑关卡 (1, 4)。该关卡的最优得分为 3，激活格子的变化如下：

$$(1, 4, 2, 3) \xrightarrow{R} (2, 3) \xrightarrow{L} (2) \xrightarrow{R} ()$$

各个关卡的最大得分分别为：

• 对 (1, 1)，得分为 1
• 对 (2, 2)，得分为 1
• 对 (4, 4)，得分为 1
• 对 (1, 2)，得分为 2
• 对 (1, 4)，得分为 3
• 对 (2, 4)，得分为 3