物资准备

题目描述

某国测试一种新型火炮，对一条路线进行打击。 这条路线上有n个据点，每个据点都有一个牢固值，1发炮弹消耗1点牢固值，假设牢固值为10的据点，需要10发炮弹摧毁。 现在共有m门火炮参与测试，每门火炮摧毁一段连续范围的据点。 由于指挥混乱，m门火炮发射前没有沟通，可能存在炮弹浪费的情况。 问合计需要准备多少发炮弹。

输入格式

输入描述 第一行包括两个整数n和m。（1≤n,m≤100000） 第二行包括n个整数，依次表示n个据点的牢固值。（1≤整数≤100） 接下来m行，每行两个正整数L和R，表示一门火炮的摧毁范围。（1≤L≤R≤n）

输出格式

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

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

27

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

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$ 发炮弹。

来源

童程童美