Problem F
GME Stonks
Elon Fusk wants to make stonks on the stock market, so he decides that he will trade some GME stocks today.
Mr. Fusk is very active on Twitter. Immediately after performing any trade he will tweet about it. His large Twitter following pays great attention to his tweets which causes the market price of GME to change dramatically after each of his trades. In fact, the market price of GME only changes when Elon tweets about his trades.
Fortunately for Elon he has a very good understanding of how his trades and tweets influence the price of GME, and wants to exploit it for maximum profit. He has prepared a list of trades he intends to perform, but needs to decide in what order to execute them.
Each trade Elon performs can be described by one integer indicating how many shares Elon buys or sells in the trade and one integer indicating how much the price will change after he tweets about it.
Elon starts with 0 shares of GME and its current market price is 0. After performing all of his trades he will sell off (or buy back) his remaining shares for the market price at the time without tweeting about it so that in the end he has no shares of GME.
Find out how much money he can make at the end of this trading session by choosing an optimal order to perform the trades.
It is possible for Elon to have a negative amount of shares in GME. It is also possible for the price of GME to be negative. All trades need to be performed. The answer might be negative.
Input
The first line of the input contains a single integer $ 1 \leq N \leq 100 \, 000 $, the number of trades Elon will make.
Then follows $N$ lines representing one trade each. Each line consists of two integers $ -10 \, 000 \leq S \leq 10 \, 000$ representing how many shares Elon will buy or sell in the trade, and $ -10 \, 000 \leq P \leq 10 \, 000$ representing how the price will change as a result of the tweet afterwards.
Output
A single integer, the maximal amount of money Elon Fusk can make in the trading session, if he orders his trades optimally.
Scoring
|
Group |
Points |
Limits |
|
1 |
6 |
$N \leq 10$ |
|
2 |
13 |
$N \leq 1\, 000$ and $0 \leq S,P$ |
|
3 |
11 |
Each trade $(S,P)$ will either have $S=0$ or $P=0$ |
|
4 |
20 |
$N \leq 1\, 000$ |
|
5 |
50 |
No further restrictions |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 5 8 -2 -10 |
44 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 -7 -2 10 3 4 |
57 |
