ژنرال باخ خود را برای جنگی تازه آماده می‌کند. او تصمیم دارد که در این جنگ، نیروهای خود را در قلعه نگاه دارد و از آن‌جا دفاع کند. نقشه قلعه به صورت یک جدول $n\times n$ است که برخی از خانه‌های آن خالی و برخی از خانه‌های آن دیوار است. یک پایگاه به یک مجموعه از خانه‌های خالی گفته می‌شود که از هر کدام از آن‌ها بتوان با طی کردن تنها خانه‌های خالی به دیگری رسید. چون که پایگاه‌ه به وسیله دیوارها از یک‌دیگر جدا شده‌اند، در هنگام جنگ با یک‌دیگر ارتباط ندارند و بنابراین هر کدام از آن‌ها نیاز به یک فرمانده دارند. اما چون ژنرال تنها $k$ فرمانده دارد، بنابراین نیاز دارد که تنها $k$ پایگاه داشته باشد. بنابراین باید با متصل کردن پایگاه‌ها به یک‌دیگر، تعداد آن‌ها را کاهش دهد. به دلیل فرسوده بودن قلعه، ژنرال تصمیم گرفته است که به جای خراب کردن دیوار‌های بین پایگاه‌ها، آن‌ها را با استفاده از پل به یک‌دیگر متصل کند. یک پل به طول $L$ پلی است که بر روی $L$ دیوار متوالی ساخته می‌شود. توجه کنید که زیر هر پل باید کاملا دیوار قرار داشته باشد و همچنین یک پل یا به صورت شرقی-غربی قرار دارد یا به صورت شمالی-جنوبی. همچنین هیچ دو پلی در یک ارتفاع ساخته نمی‌شوند. به این معنی که اگر یک پل شرقی-غربی با یک پل شمالی-جنوبی تقاطع داشته باشند، یکی از آن‌ها بر روی دیگری رد می‌شوند و کسی نمی‌تواند از روی یک پل به دیگری برود. کشیدن یک پل به طول $L$، $L$ سکه طلا خرج دارد. حال ژنرال می‌خواهد با کم‌ترین هزینه کاری کند که تعداد پایگاه‌ها کم‌تر مساوی تعداد فرماندهان شود اما از آن‌جا که از مسائل بهینه‌سازی خیلی سر در نمی‌آورد، از شما خواسته است که این کار را برای او انجام دهید.

• در سطر اول ورودی، $n$ ابعاد نقشه ($1\leq n \leq 10^2$) و سپس $k$ تعداد فرماندهان ژنرال آمده است.
• در $n$ سطر بعد، در هر سطر یک رشته به طول $n$ از $W$ و $E$ آمده است که $W$ نشان‌دهنده دیوار است و $E$ نشان‌دهنده‌ی خانه خالی است. البته در نقشه، همواره سطر اول و آخر و ستون اول و آخر دیوار هستند که در واقع همان دیوارهای دور قلعه هستند.

در تنها سطر خروجی شما باید کم‌ترین تعداد سکه‌ای که ژنرال باید مصرف کند تا تعداد پایگاه‌ها کم‌تر مساوی $k$ شود را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

• سوال بعد
• سوال قبل