GoncaSoft is an internet company that runs many services and has data centers worldwide. Each data center has a number of available machines. For security and redundancy reasons, one or more copies of each service are running at the same time. Each copy runs in a separate data center, and requires a number of machines to run on. All the copies of a given service require the same number of machines.
When GoncaSoft plans to launch a new service that requires copies, each running on machines, it sorts the data centers in descending order by their current available machines, and then uses machines in each of the top data centers. Please calculate the remaining available machines in the data centers after launching services in a given order.
Input Specification
The first line of the input contains two space-separated integers and , representing the number of data centers GoncaSoft has and the number of new services GoncaSoft wants to launch. The next line contains space-separated integers, representing the number of available machines in each of the data centers, before any services are launched. The next lines describe the services that will be launched: the -th line contains two space-separated integers and , representing the number of machines and the number of copies the -th service requires.
Output Specification
Output one line containing space-separated integers sorted in descending order, representing the number of remaining available machines in the data centers after all services have launched.
Constraints
- and .
- Each data center has at most machines initially.
- for each service such that .
- , for each service such that . The data centers will always have enough machines for the new services.
Subtasks
- Subtask 1 (12 points): , .
- Subtask 2 (12 points): , .
- Subtask 3 (9 points): , .
- Subtask 4 (26 points): Each data center has initially at most machines.
- Subtask 5 (18 points): for all services from to .
- Subtask 6 (23 points): No further constraints.
Sample Input
5 4
20 12 10 15 18
3 4
4 1
1 3
4 2
Sample Output
11 10 10 9 8
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 10 | Use 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. |
Service #4: after launching | 10 8 11 10 9 | Use 4 machines in each of the top 2 data centers. |
End | 11 10 10 9 8 | Sort the data centers in descending order. |
Comments