Up You Go

imAnik BUET Inter University Pro...
Limits 1s, 512 MB

Arya is taking part in a game of throwing marbles upwards. There are nn participants in this game in total, where Arya is the participant with label 11. Each participant is given a marble and initially each of the marbles are held at ground level (height 00). Each participant xx throws his marble straight upwards at time sxs_x with initial velocity uxu_x and it drops back on the ground after some time.

The marble will follow basic rules of physics while travelling in the air. So if a marble hasn't yet dropped back on the ground and tt time units have passed since it was thrown with initial velocity uu, its current velocity vv and current height hh can be expressed as follows:

v=ugtv = u - gt

h=ut0.5gt2h = ut - 0.5 * gt^2

Here, g=10g=10.

You have to answer qq queries, where you will be given an integer TT in each query.

For each query, count how many marbles have a strictly greater height than Arya's marble at time TT.

Input

First line of the input contains two space-separated integers nn and qq, denoting the number of participants and the number of queries.

Next nn lines each contains two integers sxs_x and uxu_x, denoting when participant xx threw the marble and its initial velocity.

Next qq lines each contains one integer TT, denoting the query time.

1n,q1051 \le n, q \le 10^5

1ux1081 \le u_x \le 10^8

0sx,T1080 \le s_x, T \le 10^8

Output

For each query, output a single line containing one single integer denoting the number of marbles with a strictly greater height than Arya's marble at the query time.

Sample

InputOutput
5 10
5 40
4 50
3 50
2 50
1 50
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
4
4
4
3
3

Submit

Login to submit.

Statistics

43% Solution Ratio
MrBrionixEarliest, 5d ago
MrBrionixFastest, 0.0s
AST_TheCoderLightest, 11 MB
MrBrionixShortest, 1712B
Toph uses cookies. By continuing you agree to our Cookie Policy.