题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day2 T1. Data Centers

GoncaSoft 是一家互联网公司，运营着众多服务，全球共有 $n$ 个数据中心。每个数据中心有一定数量的可用机器。为了保证安全性和冗余，每项服务都会同时运行一个或多个副本，每个副本运行在不同的数据中心，且需要一定数量的机器。同一服务的所有副本所需的机器数量相同。

当 GoncaSoft 计划推出一个新服务 $i$，需要 $c_{i}$ 个副本，每个副本占用 $m_{i}$ 台机器时，会先按当前可用机器数量从多到少对数据中心排序，然后在排名前 $c_{i}$ 的数据中心中各使用 $m_{i}$ 台机器。

请你计算在按给定顺序推出 $s$ 个服务后，各数据中心剩余的可用机器数量。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $s$，分别表示 GoncaSoft 拥有的数据中心数量和新服务的数量。

第二行包含 $n$ 个空格分隔的整数，表示在推出任何服务前，$n$ 个数据中心各自的可用机器数量。

接下来 $s$ 行描述将要推出的服务：第 $i$ 行包含两个空格分隔的整数 $m_{i}$ 和 $c_{i}$，分别表示第 $i$ 个服务每个副本需要的机器数量和副本数量。

输出格式

输出一行，包含 $n$ 个按降序排列的空格分隔整数，表示所有服务推出后，各数据中心剩余的可用机器数量。

5 4
20 12 10 15 18
3 4
4 1
1 3
4 2

11 10 10 9 8

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 100000$ 且 $0 \leq s \leq 5000$
• 每个数据中心初始最多有 $10^{9}$ 台机器
• 对于每个服务 $i$（$1 \leq i \leq s$），$1 \leq m_{i} \leq 10^{9}$
• 对于每个服务 $i$（$1 \leq i \leq s$），$1 \leq c_{i} \leq n$
• 数据中心始终有足够的机器支持新服务

详细子任务附加限制及分值如下表所示。