410794: GYM104114 J Joyful Death

You are Psycho Cookmaster, a devil-possessed spirit with a surprisingly humble love for food. Tonight is the opening night of your brand new restaurant – "Food to Die For" – and it's already full with reservations from $$$n$$$ elves! The $$$i$$$-th elf has a current sickness of $$$s_i$$$.

The $$$n$$$ elves will come in order tonight for their unforgettable dinner. To avoid having surprises, you have prepared $$$m$$$ dishes in advance, each of them having a health index $$$h_i$$$ and a tastiness index of $$$t_i$$$. If an elf $$$x$$$ eats a dish $$$y$$$ such that $$$h_y < s_x$$$, then elf $$$x$$$ will die.

Tonight is a great opportunity to show your evil side; after all, you are a psychopath god! Consequently, you want to distribute the $$$m$$$ dishes such that the elves that eat them will die, but you also want to show them some remorse and your love for tasty feasts. Therefore, you decided to give the elves that are going to die delicious food so that they will die with no regret. The elves that wouldn't die will have their reservations cancelled, and receive a nifty coupon to spend some other day at your restaurant.

In other words, your goal is to distribute some of the dishes amongst some of the elves (possibly none), such that the sum of tastiness of the dishes eaten by the elves that are going to die is as large as possible.

The only issue is that you do not know when the so-called 'good gods' might interfere with your plan. Therefore, knowing that the $$$n$$$ elves will come to the restaurant in order, you have to solve this problem independently for the first $$$i$$$ elves, for all $$$1 \leq i \leq n$$$.

The first line of the input contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 200\:000$$$) – the number of elves and the number of dishes, respectively.

The second line of the input contains $$$n$$$ positive integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^9$$$)  — the sickness of each elf.

Finally, the $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$h_i$$$ and $$$t_i$$$ ($$$1 \leq h_i, t_i \leq 10^9$$$)  — the health index and the tastiness index of dish $$$i$$$.

Output $$$n$$$ integers, the $$$i$$$-th of them should be the answer for the first $$$i$$$ elves.

5 3
8 10 5 1 6
6 10
5 12
9 4

12 22 22 22 26