有 n 个物品，第 i 个物品的重量是 w[i] ,价值是 v[i]，该物品的魔法值等于 w[i]*v[i] 。

有 Q 个询问，每个询问给出 4 个参数：

W1,V1,W2,V2,表示询问有多少个物品的重量在区间 [W1,W2] 范围且价值在区间 [V1,V2] 范围,输出满足条件的物品的魔法值的总和。

输入格式 多组测试数据。

第一行，一个整数 T，表示有 T 组测试数据。

每组测试数据格式如下：

第1行，N 和 Q，1<=N,Q<=10^5.

接下来有 N 行，第 i 行是w[i] 和 v[i]。（1<=w[i],v[i]<=1000）.

接下来有 Q 行，每行四个数 W1,V1,W2,V2。 （1<=W1<W2<=1000, 1<=V1<V2<=1000）。

输出格式 共 T 行，每行一个整数。

输入/输出例子1 输入：

3

2 1

2 3

3 2

1 1 3 4

5 5

1 1

2 2

3 3

4 4

5 5

3 3 6 6

2 1 4 5

1 1 2 10

1 1 100 100

1 1 3 3

3 1

999 999

999 999

999 998

1 1 1000 1000

输出：

12

50

29

5

55

14

2993004

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin>>T;
    while(T--) {
        long long N,Q;
        cin>>N>>Q;
        vector<int> w(N), v(N);
        for(int i=0;i<N;i++) 
            cin>>w[i]>> v[i];
        for(int i=0;i<Q;i++) {
            int W1, V1, W2, V2;
            cin>>W1>>V1>>W2>>V2;
            long long magic_sum = 0;
            for(int j = 0; j < N; j++) if(w[j] >= W1 && w[j] <= W2 && v[j] >= V1 && v[j] <= V2)magic_sum += w[j] * v[j];
            cout<<magic_sum << endl;
        }
    }
    return 0;
}

80分