European Girls'
Olympiad in Informatics
EGOI - 2022

DataCenters
Day2 Tasks
English (ISC)

Antalya / Türkiye

Data Centers
Problem Name

DataCenters

Input Filestandard input

Output Filestandard output

Time limit

2 seconds

Memory limit

256 megabytes

GoncaSoft is an internet company that runs many services and has n data centers worldwide. Eachdata center has a number of available machines. For security and redundancy reasons, one ormore copies of each service are running at the same time. Each copy runs in a separate datacenter, and requires a number of machines to run on. All the copies of a given service require thesame number of machines.
When GoncaSoft plans to launch a new service i that requires ci copies, each running on mimachines, it sorts the data centers in descending order by their current available machines, andthen uses mi machines in each of the top ci data centers.
Please calculate the remaining available machines in the data centers after launching s services ina given order.

Input
The ﬁrst line of the input contains two space-separated integers n and s , representing the numberof data centers GoncaSoft has and the number of new services GoncaSoft wants to launch.
The next line contains n space-separated integers, representing the number of available machines
in each of the n data centers, before any services are launched.
The next s lines describe the services that will be launched: the i th line contains two spaceseparated integers mi and ci , representing the number of machines and the number of copies theith service requires.

Output

DataCenters (1 of 3)

Output one line containing n space-separated integers sorted in descending order, representingthe number of remaining available machines in the data centers after all services have launched.

Constraints
1 ≤ n ≤ 100 000 and 0 ≤ s ≤ 5 000.
Each data center has at most 109 machines initially.
1 ≤ mi ≤ 109 for each service i such that 1 ≤ i ≤ s.
1 ≤ ci ≤ n, for each service i such that 1 ≤ i ≤ s.
The data centers will always have enough machines for the new services.

Scoring
Subtask 1 (12 points): n ≤ 100, s = 0.
Subtask 2 (12 points): n ≤ 100, s ≤ 10.
Subtask 3 (9 points): n ≤ 50 000, s ≤ 100.
Subtask 4 (26 points): Each data center has initially at most 1 000 machines.
Subtask 5 (18 points): ci = 1 for all services from 1 to s .
Subtask 6 (23 points): No further constraints.

Examplestandard input

standard output

5 4

11 10 10 9 8

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

Explanation
Step

Available Machines

Operations

Beginning

20 12 10 15 18

Service #1: before launching

20 18 15 12 10

Sort the data centers in descending order.

Service #1: after launching

17 15 12 9 10Use 3 machines in each of the top 4 data centers.

Service #2: before launching

17 15 12 10 9

Sort the data centers in descending order.

Service #2: after launching

13 15 12 10 9

Use 4 machines in the top data center.

Service #3: before launching

15 13 12 10 9

Sort the data centers in descending order.

Service #3: after launching

14 12 11 10 9

Use 1 machine in each of the top 3 data centers.

Service #4: before launching

14 12 11 10 9

Sort the data centers in descending order.

DataCenters (2 of 3)

Service #4: after launching

10 8 11 10 9

Use 4 machines in each of the top 2 data centers.

End11 10 10 9 8

Sort the data centers in descending order.

DataCenters (3 of 3)