Filmová mánie

Zadání

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í:

Maximalizovat počet shlédnutí filmu.
Mezi všemi plány optimálními z hlediska první podmínky, upřednostnit plán, který minimalizuje celkový čas potřebný na všechny přesuny mezi kiny.

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. 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, k ≤ K, prvek M_i,j reprezentuje dobu přesunu mezi kiny i a j. Platí M_i,i = 0, M_i,j = M_j,i (symetrie) a M_i,j ≤ M_i,k + M_k,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í |S − U| ≥ D (promítaní filmu se v jednom kině nikdy nepřekrývají).
Buď L_i délka seznamu začátků promítání filmu v kině i. Platí K ≤ 700, 1 ≤ D ≤ 6, TL=L₁+ … + L_K ≤ 4 × 10⁵.

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říklady

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