+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۶۴ مگابایت + منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر ---------- ژنرال باخ خود را برای جنگی تازه آماده می‌کند. او تصمیم دارد که در این جنگ، نیروهای خود را در قلعه نگاه دارد و از آن‌جا دفاع کند. نقشه قلعه به صورت یک جدول $n \times n $ است که برخی از خانه‌های آن خالی و برخی از خانه‌های آن دیوار است. یک پایگاه به یک مجموعه از خانه‌های خالی گفته می‌شود که از هر کدام از آن‌ها بتوان با طی کردن تنها خانه‌های خالی (با مجاورت ضلعی) به دیگری رسید. چون که پایگاه‌ها به وسیله دیوارها از یک‌دیگر جدا شده‌اند، در هنگام جنگ با یک‌دیگر ارتباط ندارند و بنابراین هر کدام از آن‌ها نیاز به یک فرمانده دارند. اما چون ژنرال تنها $k$ فرمانده دارد، بنابراین نیاز دارد که تنها $k$ پایگاه داشته باشد. بنابراین باید با متصل کردن پایگاه‌ها به یک‌دیگر، تعداد آن‌ها را کاهش دهد. به دلیل فرسوده بودن قلعه، ژنرال تصمیم گرفته است که به جای خراب کردن دیوار‌های بین پایگاه‌ها، آن‌ها را با استفاده از پل به یک‌دیگر متصل کند. یک پل به طول $L$ پلی است که بر روی $L$ دیوار متوالی ساخته می‌شود. توجه کنید که زیر هر پل باید کاملا دیوار قرار داشته باشد و همچنین یک پل یا به صورت شرقی-غربی قرار دارد یا به صورت شمالی-جنوبی. همچنین هیچ دو پلی در یک ارتفاع ساخته نمی‌شوند. به این معنی که اگر یک پل شرقی-غربی با یک پل شمالی-جنوبی تقاطع داشته باشند، یکی از آن‌ها بر روی دیگری رد می‌شوند و کسی نمی‌تواند از روی یک پل به دیگری برود. کشیدن یک پل به طول $L$، $L$ سکه طلا خرج دارد. حال ژنرال می‌خواهد با کم‌ترین هزینه کاری کند که تعداد پایگاه‌ها کم‌تر مساوی تعداد فرماندهان شود اما از آن‌جا که از مسائل بهینه‌سازی خیلی سر در نمی‌آورد، از شما خواسته است که این کار را برای او انجام دهید. # ورودی در سطر اول ورودی، $n$ ابعاد نقشه و سپس $k$ تعداد فرماندهان ژنرال آمده است. $$ 1 \le n \le 1\ 000 $$ در n سطر بعد، در هر سطر یک رشته به طول $n$ از $W$ و $E$ آمده است که $W$ نشان‌دهنده دیوار است و $E$ نشان‌دهنده‌ی خانه خالی است. البته در نقشه، همواره سطر اول و آخر و ستون اول و آخر دیوار هستند که در واقع همان دیوارهای دور قلعه هستند. # خروجی در تنها سطر خروجی شما باید کم‌ترین تعداد سکه‌ای که ژنرال باید مصرف کند تا تعداد پایگاه‌ها کم‌تر مساوی $k$ شود را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۰ | ۱۰۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 3 WWWWW WEWEW WWWWW WEWEW WWWWW ``` ## خروجی نمونه ۱ ``` 1 ```