题目描述

在一次电子模拟作战中，假设敌方设置了一条防线，防线上依次有n个据点。每个据点都有一个牢固值，数值越大表示越牢固。 司令部计划对n个据点进行m轮攻击，每轮攻击一段连续范围的据点，每段范围上的据点都存在一个总牢固值。 有一位最要强的飞行员，申请在总牢固值最大的一轮出战。 请你编写程序找到最大的总牢固值。

输入格式

第一行包括两个整数n和m。（1≤n,m≤500000） 第二行包括n个整数，依次表示n个据点的牢固值。（1≤整数≤100） 接下来m行，每行两个正整数L和R，表示一轮范围。（1≤L≤R≤n）

输出格式

输出一个整数，表示最大的总牢固值。

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

14

提示

输入样例中m=2，表示有2轮攻击。 第1轮攻击从3~5，总牢固值5+3+6=14。 第2轮攻击从6~7，总牢固值4+9=13。 两轮攻击总牢固值最大14。