VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Pewien handlowiec dorobił się ostatnio dużej liczby nowoczesnych budynków. Dzięki temu będzie mógł przenieść do nich stoiska handlowe, które do tej pory znajdowały się w starym, rozpadającym się domu towarowym. Nowe budynki są ustawione wzdłuż jednej ulicy, jeden obok drugiego i są ponumerowane kolejnymi liczbami całkowitymi, począwszy od 1.
Stoiska handlowe muszą być tak przeniesione, że w jednym budynku na jednym piętrze może znajdować się co najwyżej jedno z nich. Stoiska w starym budynku są ponumerowane liczbami całkowitymi od 1 do N, której to numeracji handlowiec nie chce zmieniać, żeby nie wprowadzać zamieszania. Kolejną rzeczą, mającą na celu minimalizację zamieszania, jest umieszczenie stoisk w nowych budynkach w kolejności ich numeracji - tj. stoisko o numerze większym albo musi znajdować się nad stoiskiem o numerze mniejszym, jeśli są w tym samym budynku, albo w budynku o numerze większym. Można założyć, że budynków jest tak dużo, że potencjalnie można każde stoisko umieścić w osobnym budynku, a także budynki są tak wysokie, że wszystkie stoiska mogłyby się zmieścić w jednym z nich.

Oprócz powyższych ograniczeń, handlowiec chce zminimalizować koszt czasowy jaki muszą ponieść kupujący u niego klienci, ażeby jak najbardziej uatrakcyjnić ich zakupy. W tym celu przydadzą mu się statystyki, które zebrał podczas prowadzenia starego domu. Otóż, dla każdego mieszkańca w mieście (mieszkańców nie jest dużo, więc mógł sobie na to pozwolić) ma listę stoisk, które mieszkaniec odwiedza w ciągu tygodnia (nie koniecznie w tej samej kolejności jak na liście). Handlowiec zauważył też, że mieszkańcy nie zmieniają swoich preferencji i co tydzień odwiedzają te same stoiska, oraz że wszystkie tygodniowe zakupy robią za jednym zamachem, żeby nie tracić czasu na wielokrotną podróż do domu towarowego. Można przyjąć, że tak też się będzie dziać po przejściu do nowych budynków.
Czas jaki ponosi klient robiący zakupy jest sumą czasów wejścia do budynku(ów) (oznaczany przez TE), czasów wejść o piętro wyżej (TF) oraz czasów robienia zakupów na stoisku (TS). Wszystkie trzy czasy są stałe dla każdego budynku i każdego klienta. Każdy klient zaczyna i kończy swoje zakupy na zewnątrz budynków. Zaraz po wejściu do budynku klient znajduje się na parterze (piętrze 0), na którym także może znajdować się stoisko; pozostałe piętra są tylko nad nim - nie ma pięter podziemnych. Żeby przejść do innego budynku należy najpierw wyjść z danego budynku, uprzednio schodząc na parter. Czas zejścia na piętro niżej, czas wyjścia z budynku, czas przemieszczenia się między budynkami, czas dojazdu/powrotu z/do domu do/z domu towarowego jest pomijalny i można przyjąć, że wynosi 0.

Zadanie

Masz daną liczbę stoisk, czasy wejścia, przejścia na wyższe piętra i zakupów oraz dla każdego klienta listę stoisk, które musi odwiedzić. Twój program powinien obliczyć, ile w sumie czasu muszą poświęcić wszyscy klienci w ciągu tygodnia, przy optymalnym ustawieniu stoisk w budynkach (tj. ustawieniu minimalizującym tę sumę).

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajdują się dwie liczby całkowite N i M (1 ≤ N ≤ 2.500, 1 ≤ M ≤ 1.000), oznaczające odpowiednio liczbę stoisk oraz liczbę klientów. W drugim wierszu zestawu znajdują się trzy liczby całkowite TE, TF i TS (0 ≤ TE, TF, TS ≤ 500) - są to czasy opisane w treści zadania. Kolejne M wierszy to listy stoisk odwiedzanych przez kolejnych klientów. Każdy wiersz zaczyna się od dodatniej liczby całkowitej c, będącej długością tej listy, po której następuje c numerów stoisk, posortowanych rosnąco (numery stoisk na liście danego klienta nie powtarzają się i oczywiście są liczbami całkowitymi z przedziału domkniętego od 1 do N). Łączna liczba wszystkich stoisk na wszystkich listach w danym zestawie nie przekroczy 75.000.

Specyfikacja wyjścia

Wynikiem dla każdego zestawu testowego jest wiersz zawierający jedną liczba całkowitą, będącą sumarycznym kosztem czasowym klientów, ponoszonym w ciągu tygodnia, przy optymalnym ustawieniu stoisk.

Przykład

Wejście

3
2 1
10 1 1
1 2
3 3
3 3 3
3 1 2 3
3 1 2 3
3 1 2 3
5 2
7 3 1
3 1 3 5
2 1 4

Wyjście

11
54
39