Larry and Mate

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

Larry is looking for a mate, but since his is such a busy man he is employing two of his friends to help him.

There are N candidate mates, each of which have two values: a beauty value (a_i) and a personality value (b_i).

One of Larry's friends cares about both values, and will only consider a mate for larry if their beauty is at least A and their personality is at least B.

The other of his friends cares about the overall value, and will only consider a mate for Larry if their beauty value + their personality value is at least C.

Larry doesn't know his friends' values of A, B, and C though, so given Q triplets of integers (A,B,C), he wants you to detemine how many mates will be considered a candidate by both of his friends. Can you help him?

Input Specification

The first line will contain two integers N and Q\ (1 \leq N,Q \leq 10^5).

The next N lines will contain two values a_i,b_i\ (0 \leq a_i,b_i \leq 10^9)

The next Q lines will contain three values A, B, and C\ (0 \leq A,B,C \leq 10^9).

Output Specification

You are to output Q lines: the number of mates considered to be a candidate by both of his friends for each query.


Subtask 1 (2%)

N,Q \leq 3000

Subtask 2 (20%)

a_i,b_i,A,B \leq 10^5, C=0

Subtask 3 (21%)

a_i,b_i,A,B \leq 10^5, C \leq 2\cdot 10^5

Subtask 4 (57%)

No additional constraints.

Sample Input

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

Sample Output



There are no comments at the moment.