O: Chisaki and Picnic

Chisaki, a kindergarten student, decided to bring sweets for the excursion.

There are $ N $ of sweets, and the $ i $ th sweet is priced at $ A_i $ yen and tastes $ B_i $.

Chisaki has $ M $ friends, and the $ j $ th friend cries when she has $ D_j $ or more of sweets priced at $ C_j $ or more.

Chisaki-chan will be happy if her friends cry, so I'd like to bring some sweets so that it doesn't happen.

Help Chisaki-chan to find out how much the total deliciousness of sweets can be.

input

On the first line, the number of sweets $ N $ and the number of friends $ M $ are given, separated by blanks.

Of the following $ N $ lines, $ A_i and B_i $ are given on the $ i $ line, separated by blanks.

Of the following $ M $ lines, $ C_j and D_j $ are given on the $ j $ line, separated by blanks.

output

When you choose a candy to bring so that no friend will cry, output the maximum possible value as the total taste.

Constraint

* $ N, M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 100 \ 000 $
* $ A_1, A_2, A_3, \ dots, A_N $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* $ B_1, B_2, B_3, \ dots, B_N $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* Satisfy $ A_1 \ leq A_2 \ leq A_3 \ leq \ cdots \ leq A_N $
* $ C_1, C_2, C_3, \ dots, C_M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* $ D_1, D_2, D_3, \ dots, D_M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* Satisfy $ C_1 \ leq C_2 \ leq C_3 \ leq \ cdots \ leq C_M $



Input example 1


3 1
10 1
20 2
30 3
20 2


Output example 1


Four


Bringing the $ 1 and 3 $ sweets will maximize the total deliciousness of the sweets you bring, as long as you don't make your friends cry.

If you bring both the $ 2 and 3 $ sweets, your friends will cry because you will be "bringing $ 2 $ or more of sweets that cost $ 20 $ or more".

Input example 2


5 3
10 1
20 4
30 5
40 2
50 3
20 3
30 4
40 2


Output example 2


Ten


By bringing the $ 1, 2, and 3 $ sweets, you can maximize the total deliciousness of the sweets you bring, under conditions that will not make any friends cry.





Example

Input

3 1
10 1
20 2
30 3
20 2


Output

4
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> a(n),b(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i];
  vector<Int> c(m),d(m);
  for(Int i=0;i<m;i++) cin>>c[i]>>d[i];

  {
    vector<Int> x,y;
    x.emplace_back(c[0]);
    y.emplace_back(d[0]);
    for(Int i=1;i<m;i++){
      if(y.back()<=d[i]) continue;
      if(x.back()==c[i]){
        y.back()=d[i];
      }else{
        x.emplace_back(c[i]);
        y.emplace_back(d[i]);
      }      
    }
    m=x.size();
    c=x;d=y;
  }  

  priority_queue<Int, vector<Int>, greater<Int> > pq;    
  Int j=n-1;
  for(Int i=m-1;i>=0;i--){
    while(j>=0&&a[j]>=c[i]) pq.emplace(b[j--]);
    while((Int)pq.size()>=d[i]) pq.pop();
  }
  while(j>=0) pq.emplace(b[j--]);

  Int ans=0;
  while(!pq.empty()){
    ans+=pq.top();
    pq.pop();
  }
  
  cout<<ans<<endl;
  return 0;
}

