{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003cdiv style\u003d\"float:right; width:30%; margin: 10px;\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/9c48549bf77f79049ab2f260a35b6785?v\u003d1726404384\"\u003e\n\u003cem\u003eDrake giving good city building advice.\u003c/em\u003e\u003c/div\u003e\u003cp\u003eFor many 9th grade students enthusiastically starting high school, geography is often one of the first new subjects they encounter. A very important part of geography class is teaching students about the importance of city design. The teacher explains to students how denser cities allow for more efficient transportation and use of resources. Clearly, the key to denser cities is taller buildings that house more people.\u003c/p\u003e\n\u003cp\u003eToronto, Canada is facing a housing shortage, so for the last project of the semester, the teacher goes up to the aspiring city designers and asks them to design a building that houses the most people. While all your classmates are off designing weird buildings that will probably crash and burn, your buddy Alex convinces you to use giant lego houses like all the hip kids are supposedly doing.\u003c/p\u003e\n\u003cp\u003eEach housing block is a rectangular prism with integer length, width, and height. Block \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e has a length of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/4f1cb673c07e75258a9a5cd535c1d657?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:2.383ex; height:2.509ex;\" alt\u003d\"L_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~L_i~\u003c/span\u003e\u003c/span\u003e, a width of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/df95765c65c9260a263fedcab8df16a4?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:2.993ex; height:2.509ex;\" alt\u003d\"W_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W_i~\u003c/span\u003e\u003c/span\u003e, a height of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/52607d3a870bc66c6fcacb111cde3788?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:2.731ex; height:2.509ex;\" alt\u003d\"H_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H_i~\u003c/span\u003e\u003c/span\u003e respectively and can house \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/97750191141b2daf32bdc38398535078?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:2.292ex; height:2.509ex;\" alt\u003d\"P_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~P_i~\u003c/span\u003e\u003c/span\u003e people.\u003c/p\u003e\n\u003cp\u003eUnfortunately for medieval designers, overhangs are not popular in Toronto, so they are banned by the city for aesthetic reasons. In addition, city regulations require that windows on a building are aligned by a lattice grid (aka blocks may only be rotated by \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/f878a9e4e92d56ba253afab68d71fd9f?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"90\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~90~\u003c/span\u003e\u003c/span\u003e degrees), and no block may be taller than the block below it. Formally, block \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e can be stacked on top of block \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;\" alt\u003d\"j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j~\u003c/span\u003e\u003c/span\u003e if \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/63e69a0c7e2e5db2d38eb613782983be?v\u003d1726404384\" style\u003d\"vertical-align: -1.005ex; width:7.974ex; height:2.843ex;\" alt\u003d\"L_i \\le L_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~L_i \\le L_j~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/98275a5e1d7d9dd1c827c36509bd4f1b?v\u003d1726404384\" style\u003d\"vertical-align: -1.005ex; width:9.195ex; height:2.843ex;\" alt\u003d\"W_i \\le W_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W_i \\le W_j~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a97986cf2891a5f976071b7b3e1b435c?v\u003d1726404384\" style\u003d\"vertical-align: -1.005ex; width:8.67ex; height:2.843ex;\" alt\u003d\"H_i \\le H_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H_i \\le H_j~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eYou are really interested in qualifying for the \u003cstrong\u003e\u003cem\u003egeomatics\u003c/em\u003e\u003c/strong\u003e program at the University of Waterloo, so you want to prove your geography skills to the teacher.\u003c/p\u003e\n\u003cp\u003eFind a design that houses the greatest number of people!\u003c/p\u003e\n\u003ch4\u003eInput Specification\u003c/h4\u003e\n\u003cp\u003eThe first line will contain \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/6e0cc11c968fd73892727d89119ed5f9?v\u003d1726404384\" style\u003d\"vertical-align: -0.838ex; width:14.333ex; height:2.843ex;\" alt\u003d\"(N \\le 100\\,000)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(N \\le 100\\,000)~\u003c/span\u003e\u003c/span\u003e, the number of blocks that you have available.\u003c/p\u003e\n\u003cp\u003eIn each of the next \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e lines, there will be 4 integers. On the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/cd106b0c72d8637a2b8cd9ab059b19c8?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.588ex; height:2.509ex;\" alt\u003d\"i^\\text{th}\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i^\\text{th}~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/bc84461bf31edba0d5a75659a0d49035?v\u003d1726404384\" style\u003d\"vertical-align: -0.838ex; width:12.035ex; height:2.843ex;\" alt\u003d\"(1 \\le i \\le N)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le i \\le N)~\u003c/span\u003e\u003c/span\u003e line there will be \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/6e7eeaba07b9afaf1941d9216c850b76?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:10.175ex; height:2.509ex;\" alt\u003d\"L_i, W_i, H_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~L_i, W_i, H_i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/261608b2123df4390a50f69862a91fda?v\u003d1726404384\" style\u003d\"vertical-align: -0.838ex; width:20.12ex; height:2.843ex;\" alt\u003d\"(L_i, W_i, H_i \\le 5\\,000)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(L_i, W_i, H_i \\le 5\\,000)~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/97750191141b2daf32bdc38398535078?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:2.292ex; height:2.509ex;\" alt\u003d\"P_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~P_i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d574a6d6c627b46207992bbdcd966306?v\u003d1726404384\" style\u003d\"vertical-align: -0.838ex; width:19.986ex; height:2.843ex;\" alt\u003d\"(P_i \\le 1\\,000\\,000\\,000)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(P_i \\le 1\\,000\\,000\\,000)~\u003c/span\u003e\u003c/span\u003e that specify the length, width, height in the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/cd106b0c72d8637a2b8cd9ab059b19c8?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.588ex; height:2.509ex;\" alt\u003d\"i^\\text{th}\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i^\\text{th}~\u003c/span\u003e\u003c/span\u003e block, and the number of people you can fit inside.\u003c/p\u003e\n\u003ch4\u003eOutput Specification\u003c/h4\u003e\n\u003cp\u003eOn the first line, print the greatest number of people that your building can support while adhering to regulations.\u003c/p\u003e\n\u003cp\u003eOn the next line print \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/472fbc5b7274e06adaf70c416ae15276?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.066ex; height:2.176ex;\" alt\u003d\"K\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~K~\u003c/span\u003e\u003c/span\u003e, the number of blocks in your design.\u003c/p\u003e\n\u003cp\u003eIn the next line, print \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/472fbc5b7274e06adaf70c416ae15276?v\u003d1726404384\" style\u003d\"vertical-align: -0.338ex; width:2.066ex; height:2.176ex;\" alt\u003d\"K\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~K~\u003c/span\u003e\u003c/span\u003e space separated integers indicating the indices of blocks you plan to use. You should first print the blocks from the base upwards.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eNOTE:\u003c/strong\u003e Block indices start at 1.\u003c/p\u003e\n\u003ch4\u003eConstraints\u003c/h4\u003e\n\u003ch5\u003eSubtask 1 [10%]\u003c/h5\u003e\n\u003cp\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/1544ac085740752f45cfc1598d0b0219?v\u003d1726404384\" style\u003d\"vertical-align: -0.505ex; width:6.325ex; height:2.343ex;\" alt\u003d\"N \\le 9\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N \\le 9~\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\n\u003ch5\u003eSubtask 2 [10%]\u003c/h5\u003e\n\u003cp\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/151729813b0cd4361563057de274291c?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:14.304ex; height:2.509ex;\" alt\u003d\"L_i \u003d W_i \u003d H_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~L_i \u003d W_i \u003d H_i~\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\n\u003ch5\u003eSubtask 3 [20%]\u003c/h5\u003e\n\u003cp\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/8f025825a0ed61236ba1cbbf6b03df2b?v\u003d1726404384\" style\u003d\"vertical-align: -0.505ex; width:8.65ex; height:2.343ex;\" alt\u003d\"N \\le 500\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N \\le 500~\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\n\u003ch5\u003eSubtask 4 [20%]\u003c/h5\u003e\n\u003cp\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0dcb85cdd3ab5115509ff810b2650b11?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:6.992ex; height:2.509ex;\" alt\u003d\"H_i \u003d 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H_i \u003d 1~\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\n\u003ch5\u003eSubtask 5 [20%]\u003c/h5\u003e\n\u003cp\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0139496049cf2f7a3b0911bbc705c974?v\u003d1726404384\" style\u003d\"vertical-align: -0.671ex; width:14.545ex; height:2.509ex;\" alt\u003d\"L_i, W_i \\le 1\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~L_i, W_i \\le 1\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\n\u003ch5\u003eSubtask 6 [20%]\u003c/h5\u003e\n\u003cp\u003eNo additional constraints.\u003c/p\u003e\n\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\n1 100 1 4\n2 2 1 5\n2 4 2 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n2\n3 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eSample Explanation 1\u003c/h4\u003e\n\u003cp\u003eBlock 2 is stacked on top of block 3. This is allowed since no dimension of block 2 exceeds that of block 3. When combined, the building can house \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c51b5445910d0affd9896fd64d481cfd?v\u003d1726404384\" style\u003d\"vertical-align: -0.505ex; width:10.589ex; height:2.343ex;\" alt\u003d\"5+6\u003d11\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~5+6\u003d11~\u003c/span\u003e\u003c/span\u003e people.\u003c/p\u003e\n\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\n8 8 8 3\n8 8 4 4\n5 5 5 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n2\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eSample Explanation 2\u003c/h4\u003e\n\u003cp\u003eThe optimal solution would be to stack block 3 on top of block 1. Even though stacking block 3 on top of block 2 would allow \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9271fa7e4f537aabb94733a259f63b07?v\u003d1726404384\" style\u003d\"vertical-align: -0.505ex; width:9.426ex; height:2.343ex;\" alt\u003d\"4+5\u003d9\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~4+5\u003d9~\u003c/span\u003e\u003c/span\u003e housing units, city regulation does not allow blocks to be stacked on other blocks shorter than them.\u003c/p\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}