物资准备

题目描述

某国测试一种新型火炮，对一条路线进行打击。

这条路线上有n个据点，每个据点都有一个牢固值，1发炮弹消耗1点牢固值，假设牢固值为10的据点，需要10发炮弹摧毁。

现在共有m门火炮参与测试，每门火炮摧毁一段连续范围的据点。

由于指挥混乱，m门火炮发射前没有沟通，可能存在炮弹浪费的情况。

问合计需要准备多少发炮弹。

输入格式

第一行包括两个整数n和m。（1≤n,m≤100000）

第二行包括n个整数，依次表示n个据点的牢固值。（1≤整数≤100）

接下来m行，每行两个正整数L和R，表示一门火炮的摧毁范围。（1≤L≤R≤n）

输出格式

输出一个整数，表示炮弹总数。

样例输入 #1

7 2
2 10 5 3 6 4 9
3 5
6 7

样例输出 #1

27

样例输入 #2

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

样例输出 #2

32

提示

样例1解释：

路线上有 7 个据点，2 门火炮参与。

7个据点的牢固值依次为：2，10，5，3，6，4，9。

第1门火炮摧毁第3，4，5据点，需发射炮弹数量：5+3+6=14。

第2门火炮摧毁第6，7据点，需发射炮弹数量：4+9=13。

合计需要准备 27 发炮弹。

样例2解释：

路线上有 5 个据点，3 门火炮参与。

5个据点的牢固值依次为：4，2，10，3，7。

第1门火炮摧毁第1，2据点，需发射炮弹数量：4+2=6。

第2门火炮摧毁第4，5据点，需发射炮弹数量：3+7=10。

第3门火炮摧毁第1，2，3据点，需发射炮弹数量：4+2+10=16。（无需考虑炮弹浪费的情况）

合计需要准备 32 发炮弹。

数据范围

1≤n,m≤100000

第二行的n个整数（牢固值）：1≤整数≤100

每门火炮的摧毁范围：1≤L≤R≤n

知识点与难度

本题涉及的知识点从属于 GESP 3级（一维数组、前缀和），难度等级：⭐⭐⭐⭐（Mid-）。

测试点分布