Filmová mánie

Petr se těší na premiéru dlouho očekávaného filmu. Aby si film co nejvíce užil, chce jej sledovat v kinech co nejvícekrát. Má k dispozici programy všech kin ve městě a také zná časy potřebné pro přesun mezi jednotlivými kiny. Pro zjednodušení převedl všechny časy a datumy jednotlivých představení a přesunů na celočíselné násobky vhodné časové jednotky (může se jednat například o 30 minut nebo 1 hodinu). Rád by sestavil optimální plán návštěv kin podle následujících kritérií:

Jakékoliv kino může být zvoleno jako výchozí pro celou akci. Stejně tak nezáleží, v kterém kině bude Petr sledovat film naposledy. Každé představení je potřeba absolvovat od začátku do konce. Délka promítání filmu je stejná ve všech kinech. Pokud doba potřebná na přesun z kina A do kina B je U časových jednotek a představení v kině A končí v čase T, potom je možné stihnout včas promítání filmu v kině B pouze tehdy, když film začíná v B nejdříve v čase T+U. Pokud jde o jídlo a spánek, nedělá si s tím Petr žádné starosti. Předpokládá, že může bez problémů jíst během představení a spát buď během přesunů hromadnou dopravou a nebo v kinech při čekání na začátek představení.



Obrázek 1. Předpokládejme, že film trvá 2 časové jednotky a že je promítán ve 4 kinech očíslovaných 1, 2, 3 a 4. Doba cestování mezi kinem 1 a 3 nechť je 1 časová jednotka, mezi kinem 2 a 3 nechť je 2 časové jednotky a jinak 3 časové jednotky pro zbývající dvojice kin. Každý řádek na obrázku znázorňuje seznam počátků promítání filmu v kině označeném číslem v kroužku. Například v kině 4 začíná promítání filmu v časech 6, 20, 30, 35, 45, 50 a 56. Optimální plán je vyznačen pomocí růžově vybarvených obdélníčků. Potřebné přesuny mezi kiny jsou reprezentovány červenými úsečkami, přičemž u každé úsečky je uveden počet časových jednotek, které daný přesun vyžaduje. Optimální plán zahrnuje sledování filmu 15-krát a příslušná celková doba cestování je 14 časových jednotek.

Úloha

Je dána délka filmu, doba potřebná na přesun pro každou dvojici kin a seznam začátků promítání filmu v každém z kin, vše vyjádřeno jako násobky zvolené časové jednotky. Úkolem je určit počet shlédnutí filmu a celkový čas strávený při přesunech mezi kiny v případě optimálního plánu.


Vstup

První vstupní řádek obsahuje dvě celá kladná čísla K a D oddělená mezerou. Číslo K je počet kin, číslo D je délka filmu. Dalších K řádků vstupu reprezentuje řádky matice M, která udává časy potřebné na přesuny mezi kiny. Každý řádek matice sestává z K nezáporných celých čísel oddělených mezerou. Pro všechna 1 ≤ i, j, kK, prvek Mi,j reprezentuje dobu přesunu mezi kiny i a j. Platí Mi,i = 0, Mi,j = Mj,i (symetrie) a Mi,jMi,k + Mk,j (trojúhelníková nerovnost). Následuje posledních 2×K vstupních řádků reprezentujících seznamy začátků filmu v jednotlivých kinech, počínaje kinem 1 a konče kinem K. Seznam pro jedno kino je uložen na dvou po sobě jdoucích řádcích, kde první řádek obsahuje celé kladné číslo L, což je délka seznamu, a druhý řádek obsahuje L nezáporných čísel oddělených mezerou a uspořádaných vzestupně. V tomto případě každé číslo odpovídá začátku jednoho promítání filmu. Pokud S a U jsou dva po sobě jdoucí začátky, potom platí |SU| ≥ D (promítaní filmu se v jednom kině nikdy nepřekrývají).
Buď Li délka seznamu začátků promítání filmu v kině i. Platí K ≤ 700, 1 ≤ D ≤ 6, TL=L1+ ... + LK ≤ 4 × 105.

Výstup

Výstup sestává z jednoho řádku, který obsahuje dvě celočíselné hodnoty C a T oddělené mezerou. C je počet shlédnutí filmu a T je celková doba strávená cestováním mezi kiny, obojí v případě, kdy Petr postupuje podle optimálního plánu návštev kin.

Příklad 1

Vstup
3 2
0 3 1
3 0 2
1 2 0
4
1 4 16 22
5
2 7 12 14 21
5
2 10 19 22 24
Výstup
7 2

Příklad 2

Vstup
4 2
0 3 1 3
3 0 2 3
1 2 0 3
3 3 3 0
8
1 4 16 22 30 40 60 62
8
2 7 12 14 21 40 42 44
5
2 10 19 22 24
7
6 20 30 35 45 50 56
Výstup
15 14
Data a řešení Příkladu 2 jsou znázorněny na Obrázku 1.

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data