CF740B.Alyona and flowers

Little Alyona is celebrating Happy Birthday! Her mother has an array of n flowers. Each flower has some mood, the mood of i-th flower is a__i. The mood can be positive, zero or negative.

Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.

For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:

• the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,
• the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,
• the third flower adds 1·2 = 2, because he is in two of chosen subarrays,
• the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,
• the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays.

Thus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!

Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.

小 Alyona 正在庆祝她的生日！她的妈妈有一排 $n$ 朵花。每朵花都有某种“心情”，第 $i$ 朵花的心情为 $a_i$。这个心情可以是正数、零或负数。

我们定义一个子数组（subarray）为一段连续的花所构成的区间。妈妈向 Alyona 提供了一些子数组（即若干个区间）。Alyona 想从这些妈妈建议的子数组中选出若干个（可以一个都不选，也可以全选）。之后，每朵花将为其带来的幸福感贡献其心情值乘以它被包含在所选子数组中的次数。

例如，考虑如下情形：妈妈有 $5$ 朵花，它们的心情依次为 $1,\ -2,\ 1,\ 3,\ -4$。假设妈妈建议的子数组为 $(1,\ -2)$、$(3,\ -4)$、$(1,\ 3)$、$(1,\ -2,\ 1,\ 3)$（注意：此处括号内表示对应位置上的花的心情值，即分别对应下标区间 $[1,2]$、$[4,5]$、$[1,4]$、$[1,4]$；更准确地说，应理解为按位置索引的子数组：如 $(1,-2)$ 表示第 $1$ 到第 $2$ 朵花组成的子数组，依此类推）。若 Alyona 选择其中第三个和第四个子数组，则：

• 第一朵花贡献 $1 \cdot 1 = 1$，因为它恰好出现在一个被选中的子数组中；
• 第二朵花贡献 $(-2) \cdot 1 = -2$，因为它也恰好出现在一个被选中的子数组中；
• 第三朵花贡献 $1 \cdot 2 = 2$，因为它出现在两个被选中的子数组中；
• 第四朵花贡献 $3 \cdot 2 = 6$，因为它也出现在两个被选中的子数组中；
• 第五朵花贡献 $(-4) \cdot 0 = 0$，因为它未出现在任何被选中的子数组中。

因此，总共为 Alyona 增加的幸福感为 $1 + (-2) + 2 + 6 + 0 = 7$。

Alyona 希望从妈妈建议的所有子数组中选出一个子集，使得最终增加的幸福感总值尽可能大。请帮她实现这一目标！

Alyona 可以选择任意数量的子数组——包括 $0$ 个，或全部。

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — n integers _a_1, _a_2, ..., a__n ( - 100 ≤ a__i ≤ 100).

The next m lines contain the description of the subarrays suggested by the mother. The i-th of these lines contain two integers l__i and r__i (1 ≤ l__i ≤ r__i ≤ n) denoting the subarray a[l__i], a[l__i + 1], ..., a[r__i].

Each subarray can encounter more than once.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100$）—— 分别表示花朵的数量以及母亲建议的子数组数量。

第二行包含花朵的情绪值——$n$ 个整数 $a_1, a_2, \dots, a_n$（$-100 \leq a_i \leq 100$）。

接下来的 $m$ 行描述了母亲建议的子数组。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示子数组 $a[l_i],\ a[l_i + 1],\ \dots,\ a[r_i]$。

每个子数组可能出现多次。

Print single integer — the maximum possible value added to the Alyona's happiness.

输出一个整数——即 Alyona 的幸福值所能增加的最大可能值。

The first example is the situation described in the statements.

In the second example Alyona should choose all subarrays.

The third example has answer 0 because Alyona can choose none of the subarrays.

第一个样例对应题目描述中的情形。

第二个样例中，Alyona 应选择所有子数组。

第三个样例的答案为 0，因为 Alyona 可以不选择任何子数组。