海蒂和神秘博士跳出 TARDIS,发现自己身处 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$$$ 整数,即每艘飞船可以窃取的最大黄金数量,顺序与输入中给出的飞船顺序相同。
示例
输入 #1
5 4 1 3 5 2 4 0 1 4 2 2 8 9 4
输出 #1
1 9 11 9 11
注意
第一艘飞船只能攻击第一个基地。
第二艘飞船可以攻击第一和第三基地。
第三艘飞船可以攻击第一、第二、第三基地。