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 number of races. Each race has a race track that is a straight line. The th track starts from point and ends in point .
For each race, you can form separate groups. There are 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 does not have the stamina to run more than distance.
Student lives at point 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.
The first line of input will contain 2 numbers, and .
Each of next line will contain 2 numbers, and .
Each of next line will contain 2 numbers, and .
will always be the starting point of at least one student.
will be equal for all students.
Print lines; the th line containing the minimum number of students required to complete the th race.
Input | Output |
---|---|
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 For the second race, 3 -> 7, 7 -> 10 |