IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

W Patentolandii Anty-Patentowcy postanowili urządzić wielki wiec przeciwko patentom. W tym celu postawią N namiotów na trawiastym polu. Tak się złożyło, że dokładnie w tym samym miejscu rok wcześniej wielki wiec urządzili Anty-Anty-Patentowcy, którzy stawiając swoje namioty oraz wydeptując ścieżki między nimi zniszczyli mnóstwo trawy. Anty-Patentowcy miłują przyrodę, więc kilkadziesiąt e-maili na listach dyskusyjnych wystarczyło im, aby ustalić, że rozstawią tak swoje namioty, aby przyroda na tym nie ucierpiała, czyli w miejscach, gdzie rok wcześniej stały namioty Anty-Anty-Patentowców (a tak się dziwnie złożyło, że Anty-Anty-Patentowcy rok wcześniej rozstawili też dokładnie N namiotów). Następne kilkaset e-maili pozwoliło Anty-Patentowcom na kolejną decyzję: ustawią tak namioty, aby zoptymalizować sumaryczną przepływność.

Uściślijmy ten problem. Mamy N namiotów oraz N pozycji, na których można postawić namioty (jeden namiot na jednej pozycji). Anty-Patentowcy poruszają się pomiędzy namiotami. Wiemy, że przepływ ludzi pomiędzy namiotem i-tym a namiotem j-tym wynosi P[i,j]. Natomiast szerokość ścieżki pomiędzy pozycją i-tą a pozycją j-tą wynosi D[i,j]. Dla każdej uporządkowanej pary namiotów na konkretnych pozycjach iloczyn przepływu ludzi pomiędzy tymi namiotami oraz szerokość ścieżki pomiędzy pozycjami, na których stoją namioty nazwiemy przepływnością. Przykładowo, jeśli namiot nr 3 stoi na pozycji nr 2, a namiot nr 2 stoi na pozycji nr 4 oraz P[3,2]=1, P[2,3]=4 i d[2,4]=D[4,2]=3, to przepływność pomiędzy namiotem 3 oraz namiotem 2 wynosi 3, a przepływność pomiędzy namiotem 2 a namiotem 3 wynosi 12. Anty-Patentowcy chcą tak poustawiać namioty na pozycjach, aby sumaryczna przepływność pomiędzy wszystkimi uporządkowanymi parami namiotów była maksymalna.

Pewnie sobie pomyślałeś, że Anty-Patentowcy poproszą Cię, o rozwiązanie tego problemu? Nic z tych rzeczy - dla Anty-Patentowców jest to pryszcz i nie potrzebują Twojej pomocy. W zasadzie Anty-Patentowcy już go rozwiązali (wydaje im się, że optymalnie, ale mogą się, co do tego mylić). Ty jesteś szpiegiem na usługach Wielkich Firm Lobbystycznych, które nie popierają Anty-Patentowców. W Twoje ręce wpadły plany budowy namiotów i dostałeś za zadanie je popsuć.

Zadanie

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę następujących zestawów danych.

W pierwszej linii każdego zestawu danych znajdują się dwie liczby całkowite: 2≤N≤100 oraz 1≤K≤100 (ich znaczenie zostało podane w treści zadania). W następnych N liniach następują elementy tablicy P (0≤P[i,j]≤100). Po nich, w następnych N liniach następują elementy tablicy D (0≤D[i,j]≤100). W ostatniej linii zestawu danych znajduje się N liczb całkowitych R[i] (1≤R[i]≤N). R[i]=j oznacza, że Anty-Patentowcy postawili i-ty namiot na j-tej pozycji (naturalnie żadne 2 namioty nie stoją na tej samej pozycji). Można założyć, że P[i,i]=D[i,i]=0 oraz D[i,j]=D[j,i] dla każdego i,j.

Wyjście

Przykładowe wejście

1
3 3
0 9 3
2 0 1
3 2 0
0 7 2
7 0 5
2 5 0
1 2 3

Przykładowe wyjście

73

Wyjaśnienie do przykładu