Sum Metrics Within Range

In this problem, you are given a list of logs, each containing a timestamp and a metric value. You are also given several queries, where each query specifies a time range [start, end] (inclusive). For each query, compute the sum of metric values of all logs with timestamps within the range. Formally, for each query, calculate

where (t_i) and (v_i) represent the timestamp and metric value of the (i)th log respectively. Your program should read from standard input and write the results to standard output.

inputFormat

The first line of input contains two integers (n) and (q), where (n) is the number of logs and (q) is the number of queries. The next (n) lines each contain two space-separated integers, representing a log's timestamp and its metric value. The following (q) lines each contain two space-separated integers, representing the start and end of a query.

outputFormat

The output should consist of (q) lines. Each line contains one integer, which is the sum of the metric values for the corresponding query.## sample

5 3
1 5
2 3
4 7
6 2
9 1
1 5
2 6
6 9

15
12
3