题目描述

小田 正在庆祝生日快乐！她的妈妈有一个包含 $n$ 朵花的数组。每朵花都有自己的心情，第 $i$ 朵花的心情是 $a_i$ 。心情可以是正数、零或负数。

我们将子数组定义为一段连续的花朵。妈妈推荐了一些子数组。小田 想从妈妈推荐的子数组中选择几个。之后，每朵花都会给女孩带来幸福值，每朵花能带来的幸福值是 其心情乘以该花所在子数组的数量。

例如，妈妈有 $5$ 朵花，它们的心情等于 $1,-2,1,3,-4$ 。假设母亲推荐了子数组 $(1,-2)、 (3,-4)、(1,3)、(1,-2,1,3)$ 。那么，如果女孩选择了 第三个 和 第四个 子数组，那么

第一朵花 为女孩的幸福增加了 $1 \times 1 = 1$，因为它在选中的子数组中出现了一次； 第二朵花 为女孩的幸福增加了 $(-2) \times 1 = -2$，因为它在所选的子数组中出现了一次； 第三朵花 为女孩的幸福增加了 $1 \times 2 = 2$，因为它在所选的子数组中出现了两次； 第四朵花 为女孩的幸福增加了 $3 \times 2 = 6$，因为它在所选的子数组中出现了两次； 第五朵花 为女孩的幸福增加了 $(-4) \times 0 = 0$，因为它在所选的子数组中出现了零次。

这样，女孩的幸福值总共增加了 $1 + (-2) + 2 + 6 + 0 = 7$ 。小田 希望从妈妈建议的子数组中选择这样的子数组，使她的幸福值增加得尽可能大。请帮助她做到这一点！ 小田 可以选择任意数量的子数组，甚至是 $0$。

输入

第一行包含两个整数 $n$ 和 $m$（$1<=n,m<=100$），表示花朵的数量和母亲建议的子数组的数量。

第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$-100<=a_{i}<=100$），表示每朵花朵的心情。

接下来的 $m$ 行包含母亲建议的子数组的描述。第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$（$1<=l_{i}<=r_{i}<=n$），表示子数组 $a[l_{i}],a[l_{i}+1],...,a[r_{i}]$。

可能会出现多个相同的子数组。

输出

输出 小田 能得到的最大的幸福值。

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

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

2 2
-1 -2
1 1
1 2

7

16

0

Note

第一个例子是题面描述的情况。

在第二个例子中，小田 应该选择所有子数组。

在第三个例子中，答案是 $0$，不选择任何子数组。