← 返回题目列表

Codeforces · 1184/B1

B1. 医生遇见维德(简单)

中文机器翻译题面 查看原题

海蒂和神秘博士跳出 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

注意

第一艘飞船只能攻击第一个基地。

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

第三艘飞船可以攻击第一、第二、第三基地。