← 返回题目列表

Codeforces · 740/B

B. 阿廖娜和鲜花

中文机器翻译题面 查看原题

小阿廖娜正在庆祝生日快乐!她的妈妈有一排n朵花。每朵花都有一些心情,第 i 朵花的心情是 ai。情绪可以是积极的、零的或消极的。

让我们将子数组定义为一段连续的花。母亲建议了一些子数组。阿廖娜想要选择她母亲建议的几个子阵列。之后,每朵花都会将其心情乘以该花所在的所选子数组的数量来增加女孩的幸福感。

例如,考虑当母亲有 5 朵花,它们的情绪等于 1, - 2, 1, 3, - 4 的情况。假设母亲建议子数组 (1, - 2), (3, - 4), (1, 3), (1, - 2, 1, 3)。那么如果女孩选择第三个和第四个子数组则:

- 第一朵花为女孩的幸福增加了 1·1 = 1,因为他位于选定的子数组之一中,
- 第二朵花添加 ( - 2)·1 =  - 2,因为他位于所选子数组之一中,
- 第三朵花加 1·2 = 2,因为他在两个选定的子数组中,
- 第四朵花加 3·2 = 6,因为他在两个选定的子数组中,
- 第五朵花添加 ( - 4)·0 = 0,因为他不在选定的子数组中。

因此,女孩的幸福感总共增加了 1 + ( - 2) + 2 + 6 + 0 = 7。阿廖娜想从母亲建议的子数组中选择这样的子数组,这样给她的幸福带来的附加值会尽可能大。帮她做这件事!

Alyona 可以选择任意数量的子数组,甚至是 0 个或她母亲建议的全部子数组。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — 母亲建议的花数和子数组数。

第二行包含花朵心情 — n 个整数 a1, a2, ..., an (- 100 ≤ ai ≤ 100)。

接下来的 m 行包含母亲建议的子数组的描述。这些行的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n),表示子数组 a[li]、a[li + 1]、...、a[ri]。

每个子数组可以遇到多次。

输出

打印单个整数 — 为 Alyona 的幸福增加的最大可能值。

示例

输入 #1

5 4
1 -2 1 3 -4
1 2
4 5
3 4
1 4

输出 #1

7

输入 #2

4 3
1 2 3 4
1 3
2 4
1 1

输出 #2

16

输入 #3

2 2
-1 -2
1 1
1 2

输出 #3

0

注意

第一个例子是语句中描述的情况。

在第二个示例中,Alyona 应该选择所有子数组。

第三个示例的答案为 0,因为 Alyona 无法选择任何子数组。