I am trying to solve this problem :

Little girl has an array of n elements (the elements of the array are indexed starting from 1).

Also, there are "q" queries, each one is defined by a pair of integers **li, ri (1 ≤ li ≤ ri ≤ n)**. You need to find for each query the sum of elements of the array with indexes from li to ri, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

---

Input:

The first line contains two space-separated integers n (1 ≤ n ≤ 10^5) and q (1 ≤ q ≤ 10^5) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 10^5) — the array elements.

Each of the following q lines contains two space-separated integers **li and ri (1 ≤ li ≤ ri ≤ n)** — the i-th query.

---

Output:

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

```
Sample testcases:

input:
3 3
5 3 2
1 2
2 3
1 3
output
25

input
5 3
5 2 4 1 3
1 5
2 3
2 3
output
33

```

I have knowledge of Segment tree so i applied Lazy propagation approach through segment tree.

My Effort code :

```
#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <list>
#include <cmath>
#include <stack>
using namespace std;

#define scan(x) scanf("%d",&x)
#define print(x) printf("%d ",x)
#define println(x) printf("%d\n",x)
#define For(i,a,j,k) for (i = a; i < j; i+= k)
#define For_back(i,a,j,k) for (i = j; i >= a; i-= k)
#define SET(a,x) memset(a,x,sizeof(a))
#define mod 1000000007
#define inf 0x7fffffff
#define Max 2000000

typedef pair<int,int> pii;
typedef pair<pii,int> piii;

long long int tree[3*Max];
long long int lazy[3*Max];

void update(int node,int a,int b,int i,int j,long long int value)
{
    if (lazy[node]!= 0)
    {
        tree[node] += lazy[node];

        if (a != b)
        {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if (a > b || a > j || b < i)
        return;
    if (a >= i && b <= j)
    {
        tree[node] += value;
        if (a != b)
        {
            lazy[2*node] += value;
            lazy[2*node+1] += value;
        }
        return;
    }
    int mid = (a+b)/2;
    update(2*node,a,mid,i,j,value);
    update(2*node+1,mid+1,b,i,j,value);

    tree[node] = (tree[2*node]+tree[2*node+1]);
}

long long int query(int node,int a,int b,int i,int j)
{
    if (a> b || a > j || b < i) return 0;

    if (lazy[node] != 0)
    {
        tree[node] += lazy[node];
        if (a != b)
        {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if (a >= i && b <= j)
        return tree[node];
    int mid = (a+b)/2;
    long long int q1 = query(2*node,a,mid,i,j);
    long long int q2 = query(2*node+1,mid+1,b,i,j);

    return ((q1+q2));
}
int main()
{
    SET(lazy,0);
    SET(tree,0);

    int n,m;
    cin >> n >> m;
    int i,j;
    int arr[n];
    For(i,0,n,1)
    {
        cin >> arr[i];
    }
    sort(arr,arr+n);
    For(i,0,m,1)
    {
        long long int num1,num2;
        cin >> num1 >> num2;

        update(1,0,n-1,num1-1,num2-1,1);
    }
    long long int my[n];
    For(i,0,n,1)
    {   
        long long int number = query(1,0,n-1,i,i);       
        my[i] = number;
    }
    sort(my,my+n);
    long long int sum = 0;
    For_back(i,0,n-1,1){
        sum += my[i]*arr[i];
    }
    cout << sum << endl;
    return 0;   
}

```

My approach for this was simple just to do as said using segment tree and lastly print the answer.

My question is is there any simpler Algo for this ? or should i optimize my segment tree code ?