{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eYJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.\u003cbr\u003e One day, he is going to travel from city A to southeastern city B. Let us assume that A is $(0, 0)$ on the rectangle map and B $(10^9, 10^9)$. YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at $(x, y)$ now $(0\\le x\\le 10^9,0\\le y\\le 10^9)$, he will only forward to $(x+1,y)$, $(x,y+1)$ or $(x+1,y+1)$.\u003cbr\u003e On the rectangle map from $(0,0)$ to $(10^9,10^9)$, there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village $k$ on $(x_k, y_k)$ $(1\\le x_k\\le10^9, 1\\le y_k\\le10^9)$, only the one who was from $(x_k-1,y_k-1)$ to $(x_k,y_k)$ will be able to earn $v_k$ dollars.(YJJ may get different number of dollars from different village.)\u003cbr\u003e YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T$ $(1≤T≤10)$,which is the number of test cases.\u003cbr\u003e\u003cbr\u003eIn each case, the first line of the input contains an integer $N$ $(1≤N≤10^5)$.The following $N$ lines, the $k$-th line contains 3 integers, $x_k, y_k, v_k$ $(0≤v_k≤10^3)$, which indicate that there is a village on $(x_k,y_k)$ and he can get $v_k$ dollars in that village.\u003cbr\u003eThe positions of each village is distinct."}},{"title":"Output","value":{"format":"HTML","content":"The maximum of dollars YJJ can get."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n1 1 1\r\n1 2 2\r\n3 3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}