{"raw_statement":[{"iden":"problem statement","content":"We have $N$ camels numbered $1,2,\\ldots,N$. Snuke has decided to make them line up in a row.\nThe happiness of Camel $i$ will be $L_i$ if it is among the $K_i$ frontmost camels, and $R_i$ otherwise.\nSnuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.\nSolve this problem for each of the $T$ test cases given."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq N \\leq 2 \\times 10^{5}$\n*   $1 \\leq K_i \\leq N$\n*   $1 \\leq L_i, R_i \\leq 10^9$\n*   The sum of values of $N$ in each input file is at most $2 \\times 10^5$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$\n$K_1$ $L_1$ $R_1$\n$\\vdots$\n$K_N$ $L_N$ $R_N$"},{"iden":"sample input 1","content":"3\n2\n1 5 10\n2 15 5\n3\n2 93 78\n1 71 59\n3 57 96\n19\n19 23 16\n5 90 13\n12 85 70\n19 67 78\n12 16 60\n18 48 28\n5 4 24\n12 97 97\n4 57 87\n19 91 74\n18 100 76\n7 86 46\n9 100 57\n3 76 73\n6 84 93\n1 6 84\n11 75 94\n19 15 3\n12 11 34"},{"iden":"sample output 1","content":"25\n221\n1354\n\n*   In the first test case, it is optimal to line up the camels in the order $2, 1$.\n    *   Camel $1$ is not the frontmost camel, so its happiness will be $10$.\n    *   Camel $2$ is among the two frontmost camels, so its happiness will be $15$.\n*   In the second test case, it is optimal to line up the camels in the order $2, 1, 3$.\n    *   Camel $1$ is among the two frontmost camels, so its happiness will be $93$.\n    *   Camel $2$ is the frontmost camel, so its happiness will be $71$.\n    *   Camel $3$ is among the three frontmost camels, so its happiness will be $57$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}