[ARC180] D - Division into 3

D - Division into 3

Time Limit: 3 sec / Memory Limit: 1024 MB

分数: 700 分

题面

给定长度为 的整数序列 。
回答以下 个查询。

• 第 个查询：给定整数 和 。解决以下问题，对于 。
  • 将 分成三个非空的连续子序列。对于每个连续子序列，找到其元素的最大值。找到这些最大值的最小可能和。在这里，问题的限制条件要求 的长度至少为 ，所以总有至少一种将其分为三个非空的连续子序列的方法。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入：

输出

输出 行。第 行应包含第 个查询的答案。

---

输入样例 1

7 5
4 3 1 1 4 5 2
1 7
2 4
3 5
1 5
4 7

输出样例 1

10
5
6
9
8

让我们解释第一个查询。我们有 。如果你将其分成 ，连续子序列的最大值分别为 ，它们的和为 。没有办法使这个和更小，因此这个查询的答案是 。

---

输入样例 2

10 15
8 3 8 10 1 5 3 1 6 4
4 6
2 5
6 9
8 10
2 9
4 10
1 5
1 8
1 3
4 8
1 10
2 10
6 10
2 6
2 6

输出样例 2

16
14
12
11
17
17
19
14
19
14
17
17
12
16
16