{"problem":{"name":"Camel Train","description":{"content":"We have $N$ camels numbered $1,2,\\ldots,N$. Snuke has decided to make them line up in a row. The happiness of Camel $i$ will be $L_i$ if it is among the $K_i$ frontmost camels, and $R_i$ otherwise. Sn","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"aising2020_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"aising2020_e","tags":[],"sample_group":[["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","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$."]],"created_at":"2026-03-03 11:01:14"}}