Description

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPF_i ≤ 1,000; minSPF_i ≤ maxSPF_i ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPF_i (1 ≤ SPF_i ≤ 1,000). Lotion bottle i can cover cover_i cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

Input

* Line 1: Two space-separated integers: C and L

* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF_i and maxSPF_i 

* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF_i and cover_i

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

3 23 102 51 56 24 1

Sample Output

2

Source

 

/*    枚举+优先队列 　　给奶牛的minSPF从小到大排序    防晒霜从小到大排序     从最小的防晒霜枚举    把minSPF小于防晒霜的牛的maxSPF加到优先队列当中    优先队列最小值优先，取出最小值。(因为较大的maxSPF有较大的选择空间)     更新答案*/ #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;priority_queue
          
            q;struct cownode{    int minSPF,maxSPF;}cow[2510];//牛 int sun[1000000];//防晒霜 int comp(const cownode & a,const cownode & b){    return (a.minSPF
           
            >C>>L; for (int i=1;i<=C;i++) cin>>cow[i].minSPF>>cow[i].maxSPF; int sunsum=1; for (int i=1;i<=L;i++) { cin>>SPF>>cover; for (int j=sunsum;j<=sunsum+cover;j++) sun[j]=SPF; sunsum+=cover; } sunsum--; sort(cow+1,cow+C+1,comp); sort(sun+1,sun+sunsum+1); for (int i=1;i<=sunsum;i++) //枚举防晒霜 { for (j=1;j<=C;j++)//枚举牛 if(cow[j].minSPF<=sun[i]) { q.push(-cow[j].maxSPF); cow[j].minSPF=10000000;//给个极大值 再也不会进队列了 } int t=0; if (!q.empty()) t=-q.top();//注意是-的q.top(); while (t
            
             =sun[i] && t!=0) { ans++; q.pop();//别忘了删除 } } cout<
             
              <