CF1184B1.The Doctor Meets Vader (Easy)

Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $s$ spaceships, each with a certain attacking power $a$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $b$ bases, each with a certain defensive power $d$, and a certain amount of gold $g$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.

海蒂和博士从TARDIS中跳了出来，发现自己身处2018年的洛桑联邦理工学院（EPFL）。他们被冲锋队士兵团团围住，达斯·维达正步步逼近。奇迹般地，他们成功逃到了附近的一处义军基地，但博士却十分困惑。海蒂提醒他，去年HC2大赛的主题正是《星球大战》。博士顿时恍然大悟，并已准备好迎战帝国的邪恶势力！

义军拥有 $s$ 艘宇宙飞船，每艘飞船具有一定的攻击力 $a$。

他们计划派遣这些飞船摧毁帝国的基地，并夺取足量的黄金与补给，以维持义军的存续。

帝国拥有 $b$ 座基地，每座基地具有一定的防御力 $d$ 和一定数量的黄金 $g$。

一艘飞船可以攻击所有防御力 小于等于 其攻击力的所有基地。

若一艘飞船攻击某座基地，则它将夺走该基地中的全部黄金。

义军尚未决定应首先派出哪一艘飞船，因此向博士求助。他们希望知道：对每一艘飞船而言，它所能夺取的黄金总量的最大值是多少？

The first line contains integers $s$ and $b$ ($1 \leq s, b \leq 10^5$), the number of spaceships and the number of bases, respectively.

The second line contains $s$ integers $a$ ($0 \leq a \leq 10^9$), the attacking power of each spaceship.

The next $b$ lines contain integers $d, g$ ($0 \leq d \leq 10^9$, $0 \leq g \leq 10^4$), the defensive power and the gold of each base, respectively.

第一行包含两个整数 $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$），分别表示每个基地的防御力和黄金数量。

Print $s$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.

输出 $s$ 个整数，表示每艘飞船最多能窃取的黄金数量，输出顺序需与输入中飞船的顺序一致。

The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

第一艘宇宙飞船只能攻击第一座基地。

第二艘宇宙飞船可以攻击第一座和第三座基地。

第三艘宇宙飞船可以攻击第一座、第二座和第三座基地。