Pretty Boxes

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/NOV19/hindi/PBOXES.pdf), [Bengali](http://www.codechef.com/download/translated/NOV19/bengali/PBOXES.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/NOV19/mandarin/PBOXES.pdf), [Russian](http://www.codechef.com/download/translated/NOV19/russian/PBOXES.pdf), and [Vietnamese](http://www.codechef.com/download/translated/NOV19/vietnamese/PBOXES.pdf) as well. Taeyeon has a large collection of $N$ pretty boxes (numbered $1$ through $N$). For each valid $i$, the $i$th box has two attributes $S_i$ and $P_i$, representing the size and beauty of the box respectively, and it can fit inside each box $j$ such that $S_i \le S_j$. (Don't ask why a box can fit into another box with the same size.) Yoona's birthday is coming very soon, so Taeyeon decided to give Yoona some boxes as birthday gifts. As it is not cool to gift empty boxes, Taeyeon decided to put boxes inside boxes. Specifically, Taeyeon wants to choose $K$ pairs of boxes (for some valid $K$) and for each pair, put one box inside the other (if they have the same size, she can choose which box should be inside; otherwise, she puts the smaller box inside the bigger one). For each pair of boxes $(i, j)$ such that box $i$ is inside box $j$, the beauty of this pair is $P_j  P_i$, since Taeyeon would think the beauty of the inner box is wasted. Unboxing boxes is very tiring, so it is possible that Yoona does not want many pairs of boxes, and Taeyeon does not know the ideal value of $K$. Therefore, for each $K$ between $1$ and $\left\lfloor\frac{N}{2}\right\rfloor$, you need to help Taeyeon find the maximum possible total beauty she could obtain using at most $K$ pairs of boxes (the maximum possible sum of beauties of these pairs). ### Input  The first line of the input contains a single integer $N$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains two spaceseparated integers $S_i$ and $P_i$. ### Output Print $\left\lfloor\frac{N}{2}\right\rfloor$ lines. For each valid $i$, the $i$th of these lines should contain a single integer ― the maximum beauty for at most $i$ pairs. ### Constraints  $1 \le N \le 2 \cdot 10^5$  $1 \le S_i \le 2 \cdot 10^5$ for each valid $i$  $1 \le P_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (20 points):** $N \le 100$ **Subtask #2 (30 points):** $N \le 3,000$ **Subtask #3 (50 points):** original constraints ### Example Input 1 ``` 3 1 4 3 1 4 5 ``` ### Example Output 1 ``` 4 ``` ### Example Input 2 ``` 5 1 4 1 5 1 3 3 4 3 1 ``` ### Example Output 2 ``` 3 5 ``` ### Example Input 3 ``` 5 1 85 1 306 1 345 1 107 1 193 ``` ### Example Output 3 ``` 260 459 ``` ### Example Input 4 ``` 4 1 1 2 3 3 2 4 4 ``` ### Example Output 4 ``` 3 4 ```Author:  gamegame 
Editorial  https://discuss.codechef.com/problems/PBOXES 
Tags  challenge, datastructure, gamegame, mincostflow, nov19, segmenttree, watcher 
Date Added:  13102019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 