B1. Доктор Встречает Вейдера (лёгкая)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хайди и Доктор Кто выскочили из ТАРДИС и обнаружили себя в EPFL в 2018 году. Они были окружены штормовиками, и к ним приближался Дарт Вейдер. Каким-то чудом им удалось сбежать на ближайшую базу повстанцев, но Доктор был сильно смущён происходящим. Хайди напомнила ему, что в прошлом году основной темой HC2 были Звёздные Войны. После чего Доктор всё понял и приготовился встретиться лицом к лицу со злом Империи.

У повстанцев было $$$s$$$ космических кораблей, каждый с некоторой силой атаки $$$a$$$.

Они хотят отправить свои корабли, чтобы разрушить некоторые базы империи и похитить достаточное количество золота и припасов, чтобы поддержать силы восстания.

У Империи есть $$$b$$$ баз, каждая с некоторой силой защиты $$$d$$$ и некоторым количеством золота $$$g$$$.

Космический корабль может атаковать все базы, которые имеют силу защиты не превосходящую силу атаки корабля.

Если космический корабль атакует базу, то он похищает всё золото, которое там находилось.

Повстанцы не решили какой космический корабль отправить первым, так что они обратились за помощью к Доктору. Они бы хотели знать для каждого космического корабля максимальное количество золота, которое он может украсть.

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

Первая строка содержит целые числа $$$s$$$ и $$$b$$$ ($$$1 \leq s, b \leq 10^5$$$) — количество кораблей и количество баз.

Вторая строка содержит $$$s$$$ целых чисел $$$a$$$ ($$$0 \leq a \leq 10^9$$$) — силу атаки каждого корабля.

Следующие $$$b$$$ строк содержат целые числа $$$d, g$$$ ($$$0 \leq d \leq 10^9$$$, $$$0 \leq g \leq 10^4$$$) — силу защиты и количество золота у каждой базы.

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

Выведите $$$s$$$ целых чисел — для каждого корабля во входных данных выведите максимальное количество золота, которое он может украсть.

Пример
Входные данные
5 4
1 3 5 2 4
0 1
4 2
2 8
9 4
Выходные данные
1 9 11 9 11
Примечание

Первый космический корабль может атаковать только первую базу.

Второй космический корабль может атаковать первую и третью базу.

Третий космический корабль может атаковать первую, вторую и третью базы.