After a tough contest, it can be helpful to drink some coffee. Real programmers have many different types of coffee that are gradually added to one cup. We will consider coffee with a specific feature: different types of coffee are layered in the cup and do not mix.
A drink made from such types of coffee can be described as follows: there are a total of $$$n$$$ types of coffee in the cup, the $$$i$$$-th type is characterized by its strength level $$$p_i$$$ and the height of the layer it occupies in the cup, $$$h_i$$$. If $$$i \lt j$$$, then the layer of the $$$i$$$-th type of coffee is below the coffee of the $$$j$$$-th type. It is also known that the height of the cup is equal to $$$\sum\limits_{i=1}^n h_i$$$, meaning the top edge of the uppermost layer of coffee is exactly at the upper boundary of the cup.
Sometimes you want to create a drink with a specific total strength level. The total strength level is defined as the weighted average of the levels of the types of coffee poured into the cup, that is, $$$$$$P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}$$$$$$
To change $$$P$$$, one can:
- choose a straw of arbitrary height $$$h$$$;
- perform the following one or more times: put the straw into the drink to any depth from $$$0$$$ to $$$h$$$ inclusive relative to the top edge of the cup (not relative to the current liquid level) and sip an arbitrary (not necessarily whole) amount of coffee from the level where the bottom end of the straw reaches.
When sipping some amount of coffee from one layer, the height of that layer decreases by the corresponding amount, and all upper layers drop down by the same amount.
Your task is to answer queries of the form: can the current drink be turned into a drink with strength $$$t_i$$$, and if so, what is the minimum height of the straw required for this? Since it may be difficult to calculate the exact necessary height of the straw, it is sufficient to determine the minimum number of upper layers of coffee needed so that by sipping some amount of coffee from some of them, it is possible to achieve a total strength level of $$$t_i$$$.
The first line of input contains two integers $$$n$$$ and $$$q$$$ — the number of layers of coffee in the cup and the number of queries ($$$1 \le n, q \le 2 \cdot 10^5$$$).
The next $$$n$$$ lines contain two integers $$$p_i$$$ and $$$h_i$$$ each — the strength level and height of the $$$i$$$-th layer of coffee from the bottom of the cup ($$$1 \le p_i, h_i \le 10^9$$$). It is guaranteed that the sum $$$p_i \cdot h_i$$$ over all $$$i$$$ does not exceed $$$10^{18}$$$.
In the $$$i$$$-th of the next $$$q$$$ lines, there is a single integer $$$t_i$$$, defining the $$$i$$$-th query ($$$1 \le t_i \le 10^9$$$).
Output $$$q$$$ lines, in the $$$i$$$-th of which there is a single integer from $$$0$$$ to $$$n$$$ — the answer to the $$$i$$$-th query. If for some query the answer is such that the required strength level cannot be achieved, output $$$-1$$$ as the answer to that query.
3 41 13 72 41234
2 2 3 -1
For the example from the statement:
- In the first query, to obtain a drink with strength $$$1$$$, it is sufficient to sip the top two layers of coffee.
- In the second query, it is sufficient to sip some coffee from the second layer from the top.
- In the third query, it will be necessary to sip from the first and third layers of coffee.
- In the fourth query, it is impossible to achieve a strength level of $$$4$$$.
| Name |
|---|