Orkesteroptimering

Problemlösar-orkestern är en samling programmerarmusiker i full gång med att planera sin kommande turné. Den viktigaste uppgiften är att maximera oväsendet de kan åstadkomma i varje låt, detta för att uppnå optimal publikuppskattning.

Orkestern består av $N$ musiker och har bett dig att optimera en låt som består av $M$ takter. Varje musiker har endast övat på de takter han/hon funnit intressanta och är inte kapabel att spela resten av takterna. Varje gång som en musiker spelar en takt så görs detta med oväsendet $V=1/(X+1)$ oväsen-enheter, där $X$ är antalet takter som musikern spelat tidigare i låten. En musiker spelar alltså svagare och svagare ju fler takter han/hon spelar, vilket självklart beror på den ansträngning det tar att lyfta sitt instrument.

Oväsendet i en takt räknas ut genom att ta det maximala $V$ för de musiker som spelar då (endast den som spelar starkast hörs), eller $0$ om ingen spelar i takten. För att räkna ut det totala oväsendet i låten så adderar man sedan helt enkelt ihop oväsendet för alla takter. Din uppgift är att räkna ut hur mycket oväsen som kan åstadkommas i låten, givet att orkestern spelar optimalt.

Notera att alla musiker spelar lika bra, det enda som har betydelse för mängden oväsen en musiker kan åstadkomma är antalet takter han/hon har spelat tidigare.

Indata

Den första raden består av två heltal, $N$ och $M$. $N$ rader följer, var och en beskrivande en musiker. Dessa rader börjar med ett heltal $T_ i$, antal takter som musiker i övat in, och följs av $T_ i$ stycken heltal som beskriver vilka takter musikern övat på. Varje takt representeras med ett tal mellan $1$ och $M$.

Utdata

Skriv ut en rad med ett flyttal, det maximala oväsendet som kan åstadkommas i låten. Ett absolut fel mindre än $10^{-5}$ betraktas som korrekt.

Delpoäng

• För 20% av poängen gäller att $1 \leq N \leq 20$ och $1 \leq M \leq 20$.

• För 80% av poängen gäller att $1 \leq N \leq 1000$ och $20 < M \leq 1000$, samt att summan av alla $T_ i$ är mindre än $20000$.

Exempel

Anta att vi har två personer och fem takter. Person 1 kan spela alla takter, och person 2 kan bara spela de två första (se exempelindata 1). Då låter vi den andra personen spela de två takter den behärskar, och den andra personen får spela resten. Summan av alla oväsenden blir då (i taktordning) $1 + 1/2 + 1 + 1/2 + 1/3 = 10/3$.

2 5
5 1 2 3 4 5
2 1 2

3.333333

3 3
2 1 3
2 1 2
2 1 2

3