{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEmuskald was hired to design an artificial waterfall according to the latest trends in landscape architecture. A modern artificial waterfall consists of multiple horizontal panels affixed to a wide flat wall. The water flows down the top of the wall from panel to panel until it reaches the bottom of the wall.\u003c/p\u003e\u003cp\u003eThe wall has height \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e and has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e panels on the wall. Each panel is a horizontal segment at height \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e which begins at \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and ends at \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th panel connects the points \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e of the plane. The top of the wall can be considered a panel connecting the points \u003cspan class\u003d\"tex-span\"\u003e( - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, \u003ci\u003et\u003c/i\u003e)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, \u003ci\u003et\u003c/i\u003e)\u003c/span\u003e. Similarly, the bottom of the wall can be considered a panel connecting the points \u003cspan class\u003d\"tex-span\"\u003e( - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 0)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 0)\u003c/span\u003e. No two panels share a common point.\u003c/p\u003e\u003cp\u003eEmuskald knows that for the waterfall to be aesthetically pleasing, it can flow from panel \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e to panel \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/64b88c59563bae6dc4473fc8d6357220?v\u003d1719130066\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e) only if the following conditions hold: \u003c/p\u003e\u003col\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emax\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e) \u0026lt; \u003ci\u003emin\u003c/i\u003e(\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e (horizontal projections of the panels overlap); \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (panel \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e is below panel \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e); \u003c/li\u003e\u003cli\u003e there is no such panel \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e that the first two conditions hold for the pairs \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ek\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e)\u003c/span\u003e. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThen the \u003cspan class\u003d\"tex-font-style-bf\"\u003eflow\u003c/span\u003e for \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/64b88c59563bae6dc4473fc8d6357220?v\u003d1719130066\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e is equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emin\u003c/i\u003e(\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e) - \u003ci\u003emax\u003c/i\u003e(\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e, the length of their horizontal projection overlap.\u003c/p\u003e\u003cp\u003eEmuskald has decided that in his waterfall the water will flow in a single path from top to bottom. If water flows to a panel (except the bottom of the wall), the water will fall further to \u003cspan class\u003d\"tex-font-style-bf\"\u003eexactly one\u003c/span\u003e lower panel. The total amount of water flow in the waterfall is then defined as the minimum horizontal projection overlap between two consecutive panels in the path of the waterfall. Formally: \u003c/p\u003e\u003col\u003e \u003cli\u003e the waterfall consists of a single path of panels \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/4a87a0f085073e514dfcfad4bdef0648?v\u003d1719130066\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e; \u003c/li\u003e\u003cli\u003e the flow of the waterfall is the minimum flow in the path \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/4a87a0f085073e514dfcfad4bdef0648?v\u003d1719130066\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003e To make a truly great waterfall Emuskald must maximize this water flow, but there are too many panels and he is having a hard time planning his creation. Below is an example of a waterfall Emuskald wants:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/41c6d7ff9304d7e5ef89764ade1b00fb?v\u003d1719130066\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eHelp Emuskald maintain his reputation and find the value of the maximum possible water flow.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003et\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), the number of the panels excluding the top and the bottom panels, and the height of the wall. Each of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e following lines contain three space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 \u0026lt; \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003et\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), the height, left and right ends of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th panel segment.\u003c/p\u003e\u003cp\u003eIt is guaranteed that no two segments share a common point.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer — the maximum possible amount of water flow in the desired waterfall.\u003c/p\u003e"}},{"title":"Examples","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\u003e5 6\n4 1 6\n3 2 7\n5 9 11\n3 10 15\n1 13 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e6 5\n4 2 8\n3 1 2\n2 2 3\n2 6 12\n1 0 7\n1 8 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe first test case corresponds to the picture.\u003c/p\u003e"}}]}