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 space-separated integers $N$ and $M$. - $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated 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$.
|Tags||cook-off, cook107, kingofnumbers|
|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|
Fetching successful submissions