E. Ваня и параллельные миры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить максимальное число тетрадей, которые можно купить, для одного мира, ему требуется решить эту задачу для $$$m$$$ миров. К счастью, отличие всех миров заключается только в том, сколько денег есть у Вани, тогда как цены в магазинах и количество доступных для покупки тетрадей во всех мирах одинаковы.

Обратите внимание, что ограничения на $$$a_i$$$ и $$$b_i$$$ отличаются от ограничений в задаче $$$C$$$!

Помогите Ване справиться с новыми трудностями!

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) - количество магазинов и количество миров соответственно.

Во второй строке записано $$$m$$$ чисел $$$k_i$$$, где $$$k_i$$$ означает число монет Вани в $$$i$$$-м мире ($$$1 \leq k_i \leq 10^{18}$$$).

В следующих $$$n$$$ строках записано по два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i \leq 10^9$$$, $$$1 \leq b_i \leq 4*10^4$$$) – цена тетради в клеточку в $$$i$$$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно.

Выходные данные

Выведите $$$m$$$ чисел, где $$$i$$$-е число означает максимальное число тетрадей, которое может купить Ваня в $$$i$$$-м мире.

Пример
Входные данные
2 3
10 30 20
8 2
5 2
Выходные данные
2 4 3