Background

Day 2 Problem A.

Translated from EGOI2022 datacenters.

Problem Description

Gonka Software (Gongsoft) is an Internet company that runs many services and has $n$ data centers around the world. Each data center has some available machines. For security and redundancy reasons, each service runs with one or more replicas at the same time. Each replica runs in a different data center and needs some machines to run. All replicas of one service require the same number of machines.

When Gongsoft plans to launch a new service $i$ that needs $c_i$ replicas, with each replica running on $m$ machines, it sorts the data centers in descending order by the number of currently available machines, and then uses $m$ machines in each of the first $c_i$ data centers.

Output the number of machines remaining in each data center after launching $s$ services.

Input Format

The first line contains two integers $n, s$, representing the number of data centers and the number of services.

The second line contains $n$ integers $a_i$, representing the initial number of available machines in each data center.

The next $s$ lines each contain two integers $m_i, c_i$, representing the required number of machines and the number of replicas.

Output Format

Output one line with $n$ integers in descending order, representing the number of machines remaining in each data center.

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

11 10 10 9 8

Hint

Sample explanation

Constraints

For all testdata, $1\le n\le 10^5$, $0\le s\le 5\times 10^3$, $0\le a_i\le 10^9$, $1\le m_i\le 10^9$, $1\le c_i\le n$. It is guaranteed that at any time, the number of available machines in any data center is non-negative.

• Subtask 1 ($12$ points): $n\le 100$, $s=0$.
• Subtask 2 ($12$ points): $n\le 100$, $s\le 10$.
• Subtask 3 ($9$ points): $n\le 5\times 10^4$, $s\le 100$.
• Subtask 4 ($26$ points): $a_i\le 10^3$.
• Subtask 5 ($18$ points): $c_i=1$.
• Subtask 6 ($23$ points): No additional constraints.

Translated by ChatGPT 5