Pracujesz w International Collaborative Printing Company (ICPC), drukującej dokumenty, broszury i naklejki na różne kampanie. Niedawno firma kupiła nową drukarkę naklejek. Drukuje ona zaprogramowane trójkątne wzory na wielkim arkuszu. Arkusz jest siatką $M\times N$ pól, gdzie $M$ to liczba wierszy, a $N$ kolumn. Każde pole dzieli się w określony sposób na dwa trójkąty, z których niektóre są wypełniane tuszem. Przykład pokazano na rysunku 8.
Rysunek 8: Zadrukowany arkusz przed pocięciem na pojedyncze naklejki.
Naklejki są małe, więc drukuje się kilka na arkuszu, a następnie wycina. Cięcia mogą przebiegać wzdłuż granic trójkątów, ale dla zachowania jakości nie mogą przebiegać wzdłuż żadnego boku wypełnionego trójkąta. Po podziale arkusza na mniejsze części te bez wypełnionych trójkątów są wyrzucane. Każda pozostała naklejka ma co najmniej jeden wypełniony trójkąt. Wszystkie wypełnione trójkąty na niej są połączone: dla dowolnych dwóch istnieje ciąg wypełnionych trójkątów tej samej naklejki, w którym każda sąsiednia para ma przynajmniej jeden wspólny punkt. Rysunek 9 pokazuje poprawne i niepoprawne cięcia.
Rysunek 9: Naklejka najbardziej po lewej jest poprawna, pozostałe dwie nie są.
Po wycięciu naklejek ich brzegi są dodatkowo polerowane. Naklejka może mieć otwory (patrz przykład 2), których brzegi też trzeba polerować. Cięcie jest darmowe, ale polerowanie kosztuje. Brzeg naklejki opisuje zbiór odcinków: poziomych, pionowych i ukośnych. Polerowanie poziomego odcinka kosztuje $H$, a pionowego $V$. Koszty ukośne $\{D_{ij}\}$ zależą od położenia: przekątna w wierszu $i$, kolumnie $j$ ma koszt $D_{ij}$. Koszt polerowania naklejki jest sumą kosztów wszystkich odcinków brzegu. Patrz rysunki 10 i 11.
Napisz program obliczający dla każdej naklejki minimalny koszt wycięcia i polerowania. Można udowodnić, że istnieje optymalny sposób jednoczesnego wycięcia wszystkich naklejek z arkusza, tak aby każda osiągnęła jednocześnie minimalny koszt polerowania.
Rysunek 10: Obliczanie kosztu polerowania. Załóżmy $H=V=10$, a dla każdej przekątnej $D_{ij}=1$. Lewa naklejka ma 4 odcinki poziome, 4 pionowe i 6 ukośnych, więc koszt wynosi 86. Prawa kosztuje 106.
Rysunek 11: Ilustracja przykładu 2. Brzegi otworów wymagają polerowania. Koszty naklejek wynoszą odpowiednio 723, 196 i 214.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ — liczbę przypadków testowych. Pierwszy wiersz każdego przypadku zawiera $M,N,H,V$: liczbę wierszy, kolumn oraz koszty polerowania odcinka poziomego i pionowego. Kolejne $M$ wierszy zawiera napisy długości $N$ ze znaków / lub \. $j$-ty znak $i$-tego napisu określa kierunek przekątnej. Następne $M$ wierszy zawiera napisy długości $2N$. Dla pola $(i,j)$ znak $(2j+1)$ w $i$-tym napisie określa, czy lewy trójkąt jest wypełniony, a znak $(2j+2)$ — czy prawy jest wypełniony. Jeśli trójkąt jest wypełniony tuszem, znak to #, w przeciwnym razie .. Na końcu jest $M$ wierszy; $i$-ty zawiera $N$ liczb całkowitych $D_{i1},D_{i2},\ldots,D_{iN}$ — koszty polerowania przekątnych.
Ograniczenia
$1\le T\le50$.
$M\ge2$; $N\ge2$; $4\le M\times N\le10000$.
$1\le H,V,D_{ij}\le1000$ dla wszystkich $1\le i\le M$ i $1\le j\le N$.
W każdym przypadku drukarka produkuje co najmniej 1 i najwyżej 1000 naklejek.
Żaden wypełniony trójkąt nie ma boku na brzegu całego arkusza.
Wyjście
Dla każdego przypadku wypisz dwa wiersze. Pierwszy zawiera liczbę całkowitą $k$ — liczbę naklejek. Drugi zawiera $k$ liczb całkowitych $c_1,c_2,\ldots,c_k$, oznaczających minimalne koszty polerowania wszystkich naklejek, posortowane niemalejąco.
Przykład
Wejście 1
1 4 9 10 10 \////\\/\ \\/\//\// //\\/\\/\ \///\//\/ .....#...##....... .##.#.....##...##. ...#.##....####... ..#.........#..##. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Wyjście 1
2 86 106
Wejście 2
1 8 12 20 19 \//\//\/\\\/ //\/\\\///// ///\/\\\\//\ \//\\\/\/\/\ \\\\\///\/// ///\\\\\\\\\ //\/////\\\\ /////\////// ........................ ..##################.... ..##..............##.... ..##..######....##...... ..##..##......####..##.. ..##........##......##.. ..############....####.. ........................ 11 12 13 15 14 12 17 16 14 13 11 10 12 13 15 14 13 17 18 17 15 14 12 16 16 17 18 17 15 14 13 11 16 17 18 19 19 11 12 13 15 14 16 16 17 18 14 13 13 20 16 15 14 14 13 11 10 12 12 13 16 17 17 14 15 16 19 12 14 11 14 16 18 17 14 14 16 19 18 14 15 13 12 14 15 16 17 15 11 18 19 16 16 14 14 20
Wyjście 2
3 196 214 723