The Doctor Meets Vader (Easy)

题意翻译

#### 题意简述： 叛军有 $s$ 艘太空船，每艘都有一定的攻击力 $a$ 。帝国有 $b$ 个基地，每个基地都有一定的防御能力 $d$ 和一定量的金 $g$ 。 宇宙飞船可以攻击所有防御力小于等于其攻击力的飞船，与此同时，该基地的所有黄金都会被盗走。 第一行输入两个整数 $s$ ，$b$ 。 接下来 $s$ 行输入每个太空船的攻击力 $a_i$。 最后 $b$ 行输入当前基地的 $d_i$ 和 $g_i$ 输出 $s$ 个数，分别表示第 $i$ 个宇宙飞船能盗走的最大黄金。 by @初星逝者

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

5 4
1 3 5 2 4
0 1
4 2
2 8
9 4

输出样例 #1

1 9 11 9 11

说明

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.