3、吃蛋糕(cake)

[问题描述] cake.cpp

小明喜欢吃蛋糕。

小明打算以独特的方式吃蛋糕。一共有n个蛋糕排成一列,每个蛋糕的美味程度为ai,但由于小明挑食,会导致有些蛋糕美味程度为负数。他有m个吃蛋糕方案,就是选择[li,ri]这个区间吃蛋糕,且小明有个特性,吃完这个区间蛋糕他会觉得其它蛋糕的美味程度就会+1。这m个吃蛋糕方案不一定要按顺序吃,可以一直吃这个方案，但必须得吃完或不能吃为止。请你帮他求出能吃到的最大美味程度。

[输入格式] cake.in

第一行两个整数n和m,接下来的一行,有n个整数ai,最后的m'行每一行都有两个整数li和ri。

[输出格式] cake.out

输出只有一行,能吃到的最大美味程度。

[输入输出样例]

[样例提示]

对于第一个样例,只能选取[2,3]这个区间来吃蛋糕,第一次能吃到3的美味程度,第二次能吃到4的美味程度,而这之后只有一个蛋糕,不能吃了所以输出7。

对于第二个样例,如果选择第一个方案,则只能吃到10的美味程度;如果选择第二个方案,则可以两次吃完,美味程度为12。所以输出12。

[数据范围]

对于30%的数据： 2 ≤ n ≤ 10 1 ≤li ≤ ri ≤10 ai ≤ 100 。

对于70%的数据： 2 ≤ n ≤ 100 1 ≤li ≤ ri ≤100 ai ≤ 1000 。

对于100%的数据： 2 ≤ n ≤ 1000 1 ≤li ≤ ri ≤1000 ai ≤ 10000 。