Después de una dura competición, puede resultar útil tomar un poco de café. Los programadores reales tienen muchos tipos diferentes de café que se van añadiendo gradualmente a una taza. Al mismo tiempo, consideraremos el café con una característica particular: los diferentes tipos de café se guardan en la taza en "capas" y no se mezclan.

Una bebida hecha con estos tipos de café se puede describir de la siguiente manera: se vierte un total de ~n~ variedades en una taza, la ~i~-ésima variedad se caracteriza por un nivel de concentración ~p_i~ y una altura de la capa que ocupa en la taza ~h_i~. Además, si ~i < j~, entonces la capa del café ~i~-ésimo se encuentra por debajo de la capa del café ~j~-ésimo. También se sabe que la altura de la taza es ~\sum\limits_{i=1}^n h_i~, es decir, el borde superior de la capa superior de café está exactamente al nivel del borde superior de la taza.

Para variar, a veces desea obtener una bebida de un cierto nivel de concentración total de una "mezcla" de este tipo. El nivel de concentración total se determina como el promedio ponderado de los niveles de variedades vertidas en la taza, es decir, como $$\displaystyle P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} $$

Para cambiar de alguna manera a ~P~, puedes realizar la siguiente operación:

1. selecciona un absorbente de altura arbitraria ~h~;
2. haga lo siguiente una o más veces: sumérjalo en una bebida a cualquier profundidad desde ~0~ hasta ~h~ inclusive en relación con el borde superior de la taza (no en relación con el nivel de líquido actual) y beba una cantidad arbitraria cantidad de café (no necesariamente entera) desde el nivel al que llega el extremo inferior del absorbente.

Cuando se bebe una cierta cantidad de café de una capa, la altura de esta capa disminuye en la cantidad correspondiente y todas las capas superiores descienden en la misma cantidad.

Se le harán varias preguntas: ¿es posible preparar una bebida de concentración ~t_i~ a partir de la bebida actual y, de ser así, cuál es la altura mínima del absorbente necesario para ello? Dado que puede resultar difícil calcular (y evaluar) la altura ideal exacta del absorbente, se ha decidido facilitar un poco el problema, y basta con determinar el número mínimo de capas superiores de café, suficiente para que, después de beber una cierta cantidad de café de algunas de ellas, se pueda alcanzar el concentración total de la bebida ~t_i~.

Subtareas

• Subtarea 1 (5 puntos): ~q \le 100~, ~n \le 15~, ~p_i, h_i \le 100~.
• Subtarea 2 (5 puntos): ~n,q \le 500~.
• Subtarea 3 (7 puntos): ~n,q \le 2000~.
• Subtarea 4 (8 puntos): ~n,q \le 5000~.
• Subtarea 5 (15 puntos): ~p_i \le p_j~ para todo ~i < j~.
• Subtarea 6 (10 puntos): ~h_i = h_j~ para todo ~i, j~, hay como máximo dos valores de ~p_i~ diferentes.
• Subtarea 7 (10 puntos): ~h_i = h_j~ para todo ~i, j~.
• Subtarea 8 (15 puntos): ~p_i \le 10^5~ para todo ~i, j~.
• Subtarea 9 (25 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene dos números enteros ~n~ y ~q~: el número de capas de café en la taza y el número de preguntas (~1 \le n, q \le 2 \cdot 10^5~).

Las siguientes ~n~ líneas contienen cada una dos números enteros ~p_i~ y ~h_i~: el nivel de concentración y la altura de la ~i~-ésima capa de café desde el fondo de la taza (~1 \le p_i, h_i \le 10^9~). Se garantiza que la suma ~p_i \cdot h_i~ para todo ~i~ no excede ~10^{18}~.

La ~i~-ésima de las siguientes ~q~ líneas contiene un único número entero ~t_i~ que representa la ~i~-ésima pregunta (~1 \le t_i \le 10^9~).

Salida

Imprima ~q~ líneas, la ~i~-ésima de las cuales contiene un único número entero de ~0~ a ~n~: la respuesta a la pregunta ~i~ésima. Si para alguna pregunta es imposible alcanzar el nivel de concentración requerida, imprima el número ~-1~ como respuesta.

Ejemplos

Entrada 1

3 4
1 1
3 7
2 4
1
2
3
4

Salida 1

2
2
3
-1

• En la primera pregunta, para obtener una bebida de concentración ~1~, basta con beber las dos capas superiores de café.
• En la segunda pregunta, basta con beber un poco del café de la segunda capa desde arriba.
• En la tercera pregunta, se necesita beber la primera y la tercera capa de café.
• En la cuarta pregunta, es imposible alcanzar el nivel de concentración de ~4~.