The Brazilian finals of the programming marathon in $$$2021$$$ were held in the charming city of Gramado, in Rio Grande do Sul. At the end of the competition, it became clear from the scoreboard that the contest had been particularly difficult: the champion team solved $$$8$$$ problems, and the second place — still with a gold medal — solved $$$6$$$, the same number of problems solved up to the 16th place.

With so many challenges, frustrations, and cloudy weather, many participants decided to console themselves in the best way that Gramado can offer: with hot chocolate.

Among them was Naim, one of the judges responsible for creating the problems for the contest. Already full of chocolates, he began to ponder about life, about the contest... and then he had a completely random thought:

"What if I had to choose $$$K$$$ memories from that contest — represented by pairs of values $$$A_i$$$ (how much I learned) and $$$B_i$$$ (how much it hurt) — in such a way that the total sum of learnings minus the greatest suffering was as high as possible?"

As crazy as it sounds, Naim now needs your help to solve this problem urgently, before he has another hot chocolate!

Formally, you are given $$$N$$$ pairs of integers $$$(A_i,B_i)$$$. A set $$$S$$$ has a learning value given by $$$v = \sum_{i \in S} A_i - max_{i \in S} B_i$$$. For every $$$K$$$ from $$$1$$$ to $$$N$$$, you must find the maximum learning value that a set $$$S$$$ of size $$$K$$$ can have.