{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 \u0026lt;\u003d K \u0026lt;\u003d 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 \u0026lt;\u003d h_i \u0026lt;\u003d 100) and is available in quantity c_i (1 \u0026lt;\u003d c_i \u0026lt;\u003d 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 \u0026lt;\u003d a_i \u0026lt;\u003d 40000).\u003cbr\u003e\u003cbr\u003eHelp the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules."}},{"title":"Input","value":{"format":"HTML","content":"* Line 1: A single integer, K\u003cbr\u003e\u003cbr\u003e* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i."}},{"title":"Output","value":{"format":"HTML","content":"* Line 1: A single integer H, the maximum height of a tower that can be built"}},{"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\u003e3\r\n7 40 3\r\n5 23 8\r\n2 52 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e48\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":"OUTPUT DETAILS:\u003cbr\u003e\u003cbr\u003eFrom the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40."}}]}