26118번 - Data Centers 서브태스크다국어

GoncaSoft is an internet company that runs many services and has n 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 i that requires c_i copies, each running on m_i machines, it sorts the data centers in descending order by their current available machines, and then uses m_i machines in each of the top c_i data centers.

Please calculate the remaining available machines in the data centers after launching s services in a given order.

The first line of the input contains two space-separated integers n and s, representing the number of 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 space-separated integers m_i and c_i, representing the number of machines and the number of copies the i^th service requires.

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

• 1 ≤ n ≤ 100 000 and 0 ≤ s ≤ 5 000.
• Each data center has at most 10⁹ machines initially.
• 1 ≤ m_i ≤ 10⁹ for each service i such that 1 ≤ i ≤ s.
• 1 ≤ c_i ≤ n, for each service i such that 1 ≤ i ≤ s.
• The data centers will always have enough machines for the new services.