Eat Twice

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK107/hindi/EATTWICE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK107/mandarin/EATTWICE.pdf), [Russian](http://www.codechef.com/download/translated/COOK107/russian/EATTWICE.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK107/vietnamese/EATTWICE.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK107/bengali/EATTWICE.pdf) as well. Hasan has recently heard about Chef's restaurant, which serves the tastiest dishes. The restaurant has published a list of $N$ dishes (numbered $1$ through $N$) that will be served in the next $M$ days. For each valid $i$, the $i$th dish will be served only on the $D_i$th day. Hasan has investigated their tastiness and he knows that for each valid $i$, the $i$th dish has tastiness $V_i$. Hasan's budget is only large enough to try two dishes. He wants to choose these two dishes in such a way that their total (summed up) tastiness is as large as possible. However, he cannot try 2 dishes on the same day. Help Hasan and calculate the maximum possible total tastiness of the dishes he should try. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  $N$ lines follow. For each valid $i$, the $i$th of these lines contains two spaceseparated integers $D_i$ and $V_i$. ### Output For each test case, print a single line containing one integer — the maximum total tastiness. ### Constraints  $1 \le T \le 1,000$  $2 \le N, M \le 10^5$  $1 \le D_i \le M$ for each valid $i$  $1 \le V_i \le 10^9$ for each valid $i$  there are at least two dishes that are served on different days  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $M$ over all test cases does not exceed $10^6$ ### Example Input ``` 2 3 6 5 7 1 9 2 5 3 7 5 8 2 5 5 10 ``` ### Example Output ``` 16 15 ``` ### Explanation **Example case 1:** The optimal solution is to try dishes $1$ and $2$. **Example case 2:** The optimal solution is to try dishes $2$ and $3$.Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/EATTWICE 
Tags  cookoff, cook107, kingofnumbers 
Date Added:  19062019 
Time Limit:  1 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, 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