laser

Loid Forger trebuie să deblocheze un seif de înaltă securitate. Mecanismul de deblocare este protejat de un panou dreptunghiular reprezentat folosind o matrice de dimensiune $N \times M$ în care fiecare celulă conține o oglindă dispusă pe una dintre cele două diagonale.

Poziția inițială a fiecărei oglinzi este reprezentată prin caracterele $`/`$ sau $`\backslash `$.

Panoul este înconjurat de un chenar format din pereți retrovizori care reflectă orice fascicul înapoi pe direcția din care a venit (marginile funcționează ca oglinzi: cele verticale reflectă orizontal, iar cele orizontale reflectă vertical).

Un fascicul laser se deplasează doar pe direcții orizontale sau verticale prin centrele celulelor sau pe segmentele dintre centrele acestora. Mișcarea sa respectă următoarele reguli:

• fasciculul se deplasează în linie dreaptă până când întâlnește o oglindă sau un perete;
• dacă întâlnește un perete exterior, își inversează direcția (la $180^\circ$);
• dacă întâlnește o oglindă $`\backslash`$, atunci direcția se schimbă astfel (cu $90^\circ$): $\text{sus} \leftrightarrow \text{dreapta}$ respectiv $\text{jos} \leftrightarrow \text{stânga}$
• dacă întâlnește o oglindă $`/`$, atunci direcția se schimbă astfel (cu $90^\circ$): $\text{sus} \leftrightarrow \text{stânga}$ respectiv $\text{jos} \leftrightarrow \text{dreapta}$

Considerăm toate stările posibile ale fasciculului, unde o stare este determinată de o poziție și o direcție de deplasare. Se poate demonstra că, pornind din orice stare, fasciculul va reveni din nou în acea stare. Astfel, toate stările se împart în cicluri disjuncte. Numim drum de laser un astfel de ciclu.

De exemplu, pentru configurația de $2 \times 2$ de mai jos, există $5$ drumuri de laser: $4$ drumuri scurte care ating peretele exterior și un ciclu închis în centru.

Pentru fiecare celulă $(i, j)$ se cunoaște un număr întreg $C[i][j]$ care reprezeinta costul pentru a efectua o operație de flip în celula respectivă. Folosind operația flip putem roti oglinda (înlocuind $`/`$ cu $`\backslash`$ sau invers). Oglinda din fiecare celulă poate fi rotită cel mult o dată.

Scopul lui Loid este să aleagă un subset de oglinzi pentru care va aplica operația flip astfel încât:

• numărul total de drumuri de laser să fie minim posibil;
• dintre toate modurile de a ajunge într-o configurație cu un număr minim de drumuri, costul însumat al operațiilor flip să fie minim.

Date de intrare

Pe prima linie se află numerele $N$ și $M$, cu semnificația din enunț.

Următoarele $N$ linii conțin câte un șir de lungime $M$, format din caracterele $`/`$ și $`\backslash`$. Al $j$-lea caracter de pe a $i$-a linie dintre aceste $N$ reprezintă orientarea inițială a oglinzii din celula $(i, j)$

Următoarele $N$ linii conțin câte $M$ numere întregi. Al $j$-lea număr de pe a $i$-a linie dintre aceste $N$ reprezintă valoarea $C[i][j]$.

Date de ieșire

Pe prima linie se vor afișa două numere: numărul minim de drumuri de laser și costul minim total.
Pe următoarele $N$ linii se va afișa o matrice de $0$ și $1$ ($1$ pentru flip, $0$ pentru neschimbat).

Restricții și precizări

• $1 \leq N, M \leq 1000$
• $-10^9 \leq C[i][j] \leq 10^9$
• Pentru subtask-urile 1, 2, 3, 4, 5, 6, 7, 8, 9, toate costurile sunt $\geq 0$.
• Două drumuri de laser sunt distincte dacă mulțimile punctelor prin care trece fasciculul laser sunt distincte
• Dacă numărul minim de lanțuri este corect, se acordă $10\%$ din punctajul testului.
• Dacă numărul minim de lanțuri și costul minim sunt corecte, se acordă $90\%$ din punctajul testului.
• Dacă și matricea de 0/1 este corectă, se acordă $100\%$ din punctajul testului.

Exemplu 1

stdin

2 2
/\
\/
1 4
3 2

stdout

4 1
10
00

Explicație

Configurația inițială (cea din desenul de $2 \times 2$) are $5$ drumuri. Prin operarea unui flip în poziția $(1, 1)$, numărul de drumuri scade la $4$, acesta fiind minimul posibil pentru o matrice $2 \times 2$. Costul este $C[1][1] = 1$.

Exemplu 2

stdin

1 1
/
-5

stdout

2 -5
1

Explicație

Indiferent de orientarea oglinzii, există mereu $2$ drumuri. Deoarece costul rotirii este $-5$, este optim să efectuăm un flip.