{"trustable":false,"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":"\u003cdiv\u003e \u003cp\u003eНаверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта\u0026nbsp;— Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.\u003c/p\u003e \u003cp\u003eНа складах фабрики находятся \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e колец, \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-е кольцо имеет внутренний радиус \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\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\u003eb\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\u003eh\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия: \u003c/p\u003e \u003cul\u003e \u003cli\u003e Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e можно поставить на кольцо \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e только если \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003eb\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003eb\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. \u003c/li\u003e \u003cli\u003e Кольца не должны проваливаться друг в друга, то есть кольцо \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e можно поставить на кольцо \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e только если \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003eb\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e \u0026gt; \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. \u003c/li\u003e \u003cli\u003e Суммарная высота всех использованных колец должна быть максимальна. \u003c/li\u003e\u003c/ul\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"input-specification\"\u003e \u003cdiv class\u003d\"section-title\"\u003eВходные данные\u003c/div\u003e \u003cp\u003eВ первой строке входных данных записано целое число \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100 000\u003c/span\u003e)\u0026nbsp;— количество колец на складах фабрики.\u003c/p\u003e \u003cp\u003eВ \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-й из последующих \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e строк записаны три числа \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\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\u003eb\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\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\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\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 ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003eb\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026gt; \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e)\u0026nbsp;— внутренний радиус, внешний радиус и высота \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-го кольца соответственно.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Выведите максимальную высоту башни, которую смогут получить работники фабрики."}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e3\u003cbr\u003e1 5 1\u003cbr\u003e2 6 2\u003cbr\u003e3 7 3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e6\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4\u003cbr\u003e1 2 1\u003cbr\u003e1 3 3\u003cbr\u003e4 6 2\u003cbr\u003e5 7 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке 3, 2, 1.\n\u003cp\u003e\u003c/p\u003e\nВо втором примере можно либо поставить кольцо 3 на кольцо 4 и получить башню высоты 3, либо поставить кольцо 1 на кольцо 2 и получить башню высоты 4."}}]}