Probabil că toți cunoașteți povestea "Albă ca Zăpada și cei șapte pitici". Ceea ce nu știți este că, într-o zi, când piticii lucrau în mină a avut loc un cutremur și toate puțurile care coborau în mină au fost distruse. Albă ca Zăpada, văzând că piticii nu au ajuns seara acasă s-a hotărât să meargă să-i caute. Ajungând la mină, și-a dat seama că nu se putea coborî și nu știa cum să-i scoată pe pitici cât mai repede de acolo deoarece trecuse ceva timp. A găsit o hartă a minei pe care erau marcate zonele unde lucrau piticii și o mașină de săpat puțuri verticale. Presupunând că niciuna dintre aceste zone nu a fost distrusă de cutremur, Albă ca Zăpada a hotărât să sape puțuri pentru a-i elibera pe pitici.

    Ajutați-o pe Albă ca Zăpada să determine o modalitate de a săpa puțuri de lungime minimă pentru a-i scoate pe pitici din mină.

Fișierul de intrare DWARFS.IN conține pe prima linie două numere naturale M și N separate printr-un spațiu care reprezintă dimensiunile hărții.

    Pe fiecare dintre următoarele M linii se află un șir de N numere care pot fi 0 sau 1 și care nu sunt separate prin spații.

    Cifra 1 indică faptul că pe hartă, acea celulă este acoperită de pământ, iar cifra 0 indică faptul că acea celulă nu este acoperită.

    O zonă în care se pot afla pitici este formată din celule adiacente pe verticală sau orizontală care au valoarea 0 pe hartă.

    Pe hartă, în locul puțurilor a fost trecută valoarea 1, deoarece acestea au fost distruse.

Fișierul de ieșire DWARFS.OUT trebuie să conțină un singur număr natural L care reprezintă suma lungimilor tuturor puțurilor săpate. Această sumă trebuie să fie cât mai mică posibil.

  • 5 <= N, M <= 20.


  • DWARFS.IN
    8 10
    1 1 1 1 1 1 1 1 1 1
    1 1 0 1 1 1 1 1 1 1
    1 1 0 0 1 0 1 1 1 1
    1 0 0 1 1 0 0 1 0 1
    1 1 1 1 1 1 1 1 0 1
    1 0 1 1 1 1 0 0 0 1
    1 0 0 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1

    DWARFS.OUT
    5

    În continuare este reprezentată harta care conține caracterul '*' în locurile în care s-au săpat puțuri. Deci, lungimea minimă este egală cu numărul de celule marcate cu '*'.

    1 1 * 1 1 * 1 1 1 1
    1 1 0 1 1 * 1 1 1 1
    1 1 0 0 1 0 1 1 1 1
    1 0 0 1 1 0 0 1 0 1
    1 * 1 1 1 1 * 1 0 1
    1 0 1 1 1 1 0 0 0 1
    1 0 0 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1