星际争霸
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在星际争霸2游戏中，神族有一种单位叫做追猎者，人族有一种建筑叫做行星要塞，有一种通用资源叫做晶体矿，每个行星要塞内都保存着一定量的晶体矿。
现在你有 s 只追猎者，每只都有一定的攻击力 a 。人族有 b 个行星要塞，每个行星要塞都有一定的防御能力 d 和一定量的晶体矿 g 。
追猎者可以攻击所有防御力小于等于其攻击力的行星要塞，与此同时，该建筑的所有晶体矿都会被抢走。
请你求出每只追猎者能抢到的最大晶体矿总数。
注意：这是一个模拟的场景，并没有真正攻击行星要塞，也就是说追猎者之间不会相互影响结果。
注意输出要求答案放在一行中！

输入描述:

第一行输入两个整数 追猎者个数 s 与行星要塞个数 b (1 \leq s,b \leq 10^5)。
接下来一行输入每只追猎者的攻击力 a_i (0 \leq a_i \leq 10^9)。
最后 b 行输入当前行星要塞的防御力 d_i 和晶体矿 g_i 
(0 \leq d_i \leq 10^9, 0 \leq g_i \leq 10^4)

输出描述:

输出一行共 s 个数，分别表示第 i 只追猎者能抢到的最大晶体矿数量。
示例1

输入

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

输出

复制 
1 9 11 9 11

说明

第一只追猎者只能攻击第一个行星要塞。  
第二只追猎者可以攻击第一个和第三个行星要塞。  
第三只追猎者可以攻击第一、第二和第三个行星要塞。