# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Stick Race

By mainstring · Limits 1s, 512 MB

It is the annual sports event in your school. There is an event going on named ‘‘Stick Race’’.

This is basically a race between multiple groups of students. In each group, there are one or multiple students who work as a team. One student starts the race with a stick in their hand; runs some distance, and passes the stick to another student from their group. Then the second student runs some distance with the stick and passes it to the third person of their group. The race goes on like this and it ends when a student crosses the finishing line with the stick.

The event contains $R$ number of races. Each race has a race track that is a straight line. The $i$th track starts from point $A_i$ and ends in point $B_i$.

For each race, you can form separate groups. There are $M$ students available to form your groups. You can use one student in multiple races. But for each race, you can use one student only once.

Each student has the following limitations:

• Student $i$ does not have the stamina to run more than $S_i$ distance.

• Student $i$ lives at point $X_i$ aligned with the race track line. And their parents want them to start their run from home.

Your task is to build one team per race, with the least number of students who can complete the race.

The data set will be given in such way that you can build at least one team per race to complete the race.

## Input

The first line of input will contain 2 numbers, $M$ and $R$.
Each of next $M$ line will contain 2 numbers, $X_i$ and $S_i$.
Each of next $R$ line will contain 2 numbers, $A_i$ and $B_i$.

$A_i$ will always be the starting point of at least one student.

### Constraints

$1 <= M <= 100000$

$1 <= R <= 10$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

$S_i$ will be equal for all students.

$1 <= M <= 100000$

$1 <= R <= 10$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

$1 <= M <= 100000$

$1 <= R <= 100000$

$0 <= X_i <= 100000$

$1 <= S_i <= 100000$

$0 <= A_i < B_i <= 100000$

## Output

Print $R$ lines; the $i$th line containing the minimum number of students required to complete the $i$th race.

## Sample

InputOutput
6 2
5 4
8 4
3 4
7 4
10 4
9 4
5 14
3 10

3
2


For the first race, it is 5 -> 9, 9 -> 10, 10 -> 14
The student who lives in 5, goes to point 9, gives to stick to the student who lives in 9. Then that student runs to point 10 and gives the stick to another student who then runs to point 14 to finish the race.

For the second race, 3 -> 7, 7 -> 10

### Statistics

80% Solution Ratio

Um_nikEarliest, 1M ago

gryffindoFastest, 0.1s

Deshi_TouristLightest, 21 MB

Deshi_TouristShortest, 2364B