{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a01e5cb9f1dd2f4608af2a1160896712?v\u003d1715813710\" style\u003d\"float: right\" hspace\u003d\"5\"\u003eApart from the Hanging Gardens the Babylonians (around 3000-539 b.c.) built the Tower of Babylon as well. The tower was meant to reach the sky, but the project failed because of a confusion of language imposed from much higher above.\u003c/p\u003e\r\n\u003cp\u003eFor the 2638th anniversary a model of the tower will be rebuilt. \u003ci\u003en\u003c/i\u003e different types of blocks are available. Each one of them may be duplicated as many times as you like. Each type has a height \u003ci\u003ey\u003c/i\u003e, a width \u003ci\u003ex\u003c/i\u003e and a depth \u003ci\u003ez\u003c/i\u003e. The blocks are to be stacked one upon eachother so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if \u003ci\u003eboth\u003c/i\u003e of its baselines are shorter.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe number of types of blocks \u003ci\u003en\u003c/i\u003e is located in the first line of each test case. On the subsequent \u003ci\u003en\u003c/i\u003e lines the height \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, the width \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and the depth \u003ci\u003ez\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e of each type of blocks are given. There are never more than 30 different types available.\u003c/p\u003e\r\n\u003cp\u003eThere are many test cases, which come one by one. Input terminates with n \u003d 0.\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003cstrong\u003eEdited:\u003c/strong\u003e You can assume that max(\u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ez\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e) \u0026lt;\u003d 2500.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case your program should output one line with the height of the highest possible tower.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e\r\n5\r\n31 41 59\r\n26 53 58\r\n97 93 23\r\n84 62 64\r\n33 83 27\r\n1\r\n1 1 1\r\n0\r\n\r\n\u003cb\u003e\u003c/b\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n342\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}