{"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\"\u003eYou are playing a shooting game. The rules of the game are like this: You are in a two-dimensional plane and stand at $(0, 0)$. There are some obstacles above the x-axis. The location of each obstacle can be expressed as a tuple $(H, L, R)$, It means there is an obstacle at the height of $H$, interval $L$ to $R$. The $i_{th}$ obstacle with $W_i$ defense power. \u003cbr\u003e\u003cbr\u003eYou can shoot out \"Energy beam of life\". Each time you can consume $X$ vitality then shoot out an energy beam with $X$ attack power. The energy beam is a ray, When an energy beam hit an obstacle. If it\u0027s attack power not less than defense power of obstacle, it will destroy and pass through this obstacle. Otherwise it will disappear in smoke.\u003cbr\u003e\u003cbr\u003eNow you want to find an optimal strategy to destroy all obstacles and consume minimum vitality.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contain a integer $T$ (no morn than 10), the following is $T$ test case, for each test case :\u003cbr\u003e\u003cbr\u003eThe first line of each test case contains a integers n (1 $\\le$ n $\\le$ 300), number of obstacle. \u003cbr\u003e\u003cbr\u003eEach of the next n lines contains 4 integers $H_i$, $L_i$, $R_i$, $W_i$, ($1\\le H_i\\le 1,000,000,000$, $-1,000,000,000\\le L_i\\le R_i\\le 1,000,000,000$, $0\\le W_i\\le 1,000,000,000$) means information of obstacles. "}},{"title":"Output","value":{"format":"HTML","content":"For each test case output the answer as described previously."}},{"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\u003e2\r\n3\r\n1 1 2 2\r\n2 -1 1 4\r\n3 -2 -1 3\r\n3\r\n1 -1 1 2\r\n2 -1 1 3\r\n3 0 2 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eThe first testcase as shown in the picture:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/3d24fd5aaeec3d7a76c5372377dccbaf?v\u003d1726283203\"\u003e\u003c/center\u003e\u003cbr\u003e"}}]}