Dayanacaqda bir neçə avtomobil və parklama yeri var. Bütün avtomobillər üçün parklama yeri olmalıdır. Yol hərəkəti qaydalarına görə hər bir avtomobilin yalnız dayanacağın sərhədlərinə paralel və vahid zamanda bir xana sürəti ilə hərəkət etməsinə icazə verilir.

Adətən avtomobillər yaxın parklama yerinə gəlirlər. Lakin bəzi avtomobillər üçün bu yaxşı həll deyil. Növbəti dayanacağa baxaq ('C' avtomobili işarə edir, 'P' parklama yerini, 'X' divarı, '.' isə boş yeri):

.C.....P.X...

XX.......X..P

XX.....C.....

Əgər aşağıda olan avtomobil yaxın parklama yerinə doğru hərəkət edəcəksə, onda sol yuxarıdakı avtomobil başqa parklama yerinə 13 zaman vahidində çatacaq. Lakin aşağıdakı avtomobil sağ parklama yerinə gedəcəksə, onda hər iki maşın parklama yerlərinə 6 zaman vahidində gələ bilərlər.

Bütün avtomobillərin parklama yerində yerləşə biləcəyi minimal zamanı təyin edin (avtomobillər yuxarıda göstərildiyi qaydada hərəkət etməlidir). Bütün avtomobillər boş yerdən hərəkətə başlayır. Avtomobillərin sayı kifayət qədər azdır, buna görə də hər bir xanada eyni vaxta istənilən sayda avtomobil ola bilər. Avtomobillər boş və parklama yerlərindən (divarlardan deyil) gedə bilərlər. Avtomobillərin hərəkəti başa çatdıqdan sonra hər bir parklama yerində ən çox bir avtomobil ola bilər.

Giriş verilənləri

Giriş verilənləri bir neçə test ehtiva edir. Hər bir test parklama yerlərinin ölçülərini ifadə edən iki tam row və column (1 ≤ row, column ≤ 50) ədədlərini ehtiva edir. Növbəti row sətirdə parklama yeri yuxarıda göstərilmiş formatda verilir. Hər bir test üçün avtomobillərin və parklama yerlərinin sayı 100-ü aşmır.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə bütün maşınların parklama yerlərində yerləşməsinin minimal zamanını verin. Əgər bütün avtomobillərin parklama yerində yerləşməsi mümkün deyilsə, -1 verin. Əgər parklama yerində avtomobil yoxdursa, 0 verin.