Problem F
Snömur

Efter förnedringen i snöbollskriget tänker Sverige bygga en snömur, och tvinga Finland att betala för den. Muren ska ha en viss bredd $W$, och vara så hög som möjligt (it’s going to be yuuuge!).

Som byggmaterial finns det ett antal snöblock som alla har höjden 1, men kan ha olika bredder. När muren konstrueras måste varje block uppfylla följande en regel: på raden under blocket, på de två positioner blocket har sina ändpunkter, måste det ligga ett block precis till höger och vänster om punkten, undantaget början och slutet på en rad, där det istället måste finnas en ändpunkt på varje rad.

Det får dessutom inte finnas hålrum på samma position på två direkt efterföljande rader i muren (den tomma raden precis ovanför muren räknas inte).

Följande bild illustrerar några otillåtna (vänster) och tillåtna (höger) murar:

Figure 1: Ett antal otillåtna (vänster) och tillåtna (höger) murar.

Givet bredden $W$ och de möjliga blocken, konstruera en så hög mur som möjligt.

Indata

Den första raden innehåller tre heltal heltal $T$, $N$ och $W$ - testfallets nummer, antalet block och bredden på muren. Nästa rad innehåller $N$ heltal, bredden på varje block.

Du kan ladda ner alla testfall på följande länk: http://progolymp.se/uploads/snomur.zip.

Utdata

På den första raden ska du skriva ut höjden på din mur, $H$.

Du ska sedan skriva ut $H$ rader, en för varje rad i din mur. Rad $i$ ska först ha ett tal $B$, antalet block på den raden i din mur. Detta ska följas av $B$ par av heltal $P_{i,j}, L_{i,j}$ positionen och längden för det $j$:te blocket på raden.

Inskickning

När du skickar in din lösning räcker det med ett program som läser in testfallets nummer $T$ och skriver ut lösningen för det testfallet.

Om du inte vill skriva ett sådant program själv kan du använda en sida vi konstruerade: http://progolymp.se/uploads/snokaosgen.html där du kan klistra in alla dina lösningar och få ett Python 3-program som du kan skicka in.

Poängsättning

Ditt program kommer att testas på testfall, och poängsättas baserat på hur det står sig relativt domarnas lösning.

Antag att på ett testfall så får ditt program höjden $X$, och dommar lösningen får höjden $Y$. Då får du $10 \times \frac{X}{Y}$ poäng på testfallet, avrundat till två decimaler.

Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.

Din lösning kan maximalt få $100$ poäng, även om den är bättre än den domarna skrivit.