CodeForces 740B Alyona and flowers 简单暴力

原 作者 楚东方 | 发表于 | 分类于 2015级

B - Alyona and flowers
Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Description

Little Alyona is celebrating Happy Birthday! Her mother has an array of n flowers. Each flower has some mood, the mood of i-th flower is ai. The mood can be positive, zero or negative.

Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.

For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:

  • the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,
  • the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,
  • the third flower adds 1·2 = 2, because he is in two of chosen subarrays,
  • the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,
  • the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays.

Thus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!

Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — n integers a1, a2, ..., an ( - 100 ≤ ai ≤ 100).

The next m lines contain the description of the subarrays suggested by the mother. The i-th of these lines contain two integers li and ri(1 ≤ li ≤ ri ≤ n) denoting the subarray a[li], a[li + 1], ..., a[ri].

Each subarray can encounter more than once.

Output

Print single integer — the maximum possible value added to the Alyona's happiness.

Sample Input

Input 
5 4
1 -2 1 3 -4
1 2
4 5
3 4
1 4
Output 
7
Input 
4 3
1 2 3 4
1 3
2 4
1 1
Output 
16
Input 
2 2
-1 -2
1 1
1 2
Output 
0

Hint

The first example is the situation described in the statements.

In the second example Alyona should choose all subarrays.

The third example has answer 0 because Alyona can choose none of the subarrays.



简单暴力


#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  long long ll;
typedef  unsigned long long  ull; 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}

int n,m;
int a[1000];

int main()
{
	ll re = 0;
	memset(a,0,sizeof(a));
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];	
	}	
	for(int i=1;i<=m;i++)
	{
		int l,r;
		ll sum= 0; 
		cin >> l>>r;
		for(int j=l;j<=r;j++)
		{
			sum += a[j];
		 } 
		if(sum > 0)
		{
			re += sum;
		}
	}
	cout << re <<endl;
	return 0;
}