最要强的飞行员

题目描述

在一次电子模拟作战中，假设敌方设置了一条防线，防线上依次有n个据点。每个据点都有一个牢固值，数值越大表示越牢固。

司令部计划对n个据点进行m轮攻击，每轮攻击一段连续范围的据点，每段范围上的据点都存在一个总牢固值。

有一位最要强的飞行员，申请在总牢固值最大的一轮出战。

请你编写程序找到最大的总牢固值。

输入格式

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

第二行包括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

14

提示

输入样例中m=2，表示有2轮攻击。

第1轮攻击从3~5，总牢固值5+3+6=14。

第2轮攻击从6~7，总牢固值4+9=13。

两轮攻击总牢固值最大14。

数据范围

1≤n,m≤500000

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

每轮范围：1≤L≤R≤n

知识点与难度

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

测试点分布