For 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.
Toronto, 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.
Each housing block is a rectangular prism with integer length, width, and height. Block has a length of , a width of , a height of respectively and can house people.
Unfortunately 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 degrees), and no block may be taller than the block below it. Formally, block can be stacked on top of block if , and .
You are really interested in qualifying for the geomatics program at the University of Waterloo, so you want to prove your geography skills to the teacher.
Find a design that houses the greatest number of people!
The first line will contain , the number of blocks that you have available.
In each of the next lines, there will be 4 integers. On the line there will be , that specify the length, width, height in the block, and the number of people you can fit inside.
On the first line, print the greatest number of people that your building can support while adhering to regulations.
On the next line print , the number of blocks in your design.
In the next line, print space separated integers indicating the indices of blocks you plan to use. You should first print the blocks from the base upwards.
NOTE: Block indices start at 1.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [20%]
Subtask 4 [20%]
Subtask 5 [20%]
Subtask 6 [20%]
No additional constraints.
Sample Input 1
3 1 100 1 4 2 2 1 5 2 4 2 6
Sample Output 1
11 2 3 2
Sample Explanation 1
Block 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 people.
Sample Input 2
3 8 8 8 3 8 8 4 4 5 5 5 5
Sample Output 2
8 2 1 3
Sample Explanation 2
The 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 housing units, city regulation does not allow blocks to be stacked on other blocks shorter than them.