Одного зимового вечора, коли за вікном була люта зима, а в хаті було тепло й затишно, Леді вирішила поїсти.

<<У мене ще є ковбаски смачні!>> --- подумала вона, відкриваючи холодильник. Проте їй це не вдалося. Всього $t$ секунд тому кіт Васька вкрав усі $d$ ковбасок.

Не бажаючи втрачати надію і вечерю, Леді просить вашої допомоги.

Уявіть будинок Леді як прямокутник, поділений на $n$ рядків і $m$ стовпців. Введемо позначення:

\t{S} - холодильник (звідси кіт вкрав ковбаски і тут зараз знаходиться Леді);

\t{\#} - стіна;

\t{.} - порожня клітинка;

\t{P} - шафа.

Зовні кімнати також оточені стінами, але на схемі вони не позначені. І Леді, і кіт можуть подорожувати в усіх чотирьох основних напрямках, не виходячи за межі. Як тільки Леді опиниться в клітинці з шафою, кіт відразу сховається.

Кіт краде не вперше, тому Леді знає, що кіт завжди намагатиметься бігти на захід від холодильника. Він продовжуватиме рухатися прямо, поки не вдариться об стіну або в шафу. Коли він вдариться об стіну, кіт спробує повернути ліворуч, поки не знайде напрямок, щоб рухатися далі. Потрапивши в шафу, кіт залишається там і починає їсти сосиски -- по одній на секунду.

Знаючи все це, Леді вибере шлях, який дозволив би їй якомога швидше зловити кота.

Кіт спритний, тож його зловити важко -- Леді зловить кота, як тільки вони опиняться в одній клітинці з шафою. Потім Леді забере ковбаски, що залишилися на вечерю.

Кімната влаштована так, що кіт обов'язково дістанеться якоїсь шафи, коли справа доходить до ковбасок. І Леді, і коту потрібна одна секунда, щоб перейти від клітинки до клітинки. Зміна напрямку не потребує додаткового часу.

\begin{center}
\includegraphics{https://static.eolymp.com/content/ec/ec5acbc61be64a9ab5554aca2e97685c.png}
\end{center}

Давайте розглянемо наведений вище приклад. Кіт (пунктир) намагається дістатися ліворуч від холодильника, але там є стіна. Потім він повертається і намагається спуститися вниз. Оскільки внизу також є стіна, за межами позначеної межі будинку, кіт знову повертається і рухається через два клітинки праворуч. Знову вдарившись об стіну, кіт розвернувся і підбіг на одну клітинку. Потім повертається і, рухається вліво на одну клітинку, опиняється в клітину з шафою, де ховається.

Вся ця подорож для кота займає 4 секунди.

Дорога Леді зображена суцільною лінією. Рухаючись нею, це займе 2 секунди і найшвидше зловить кота.

Обчисліть, скільки ковбасок Леді може заощадити.



\InputFile

Перший рядок містить чотири числа $d$, $t$, $n$ і $m$ ($1 \leq d \leq 10^9$, $0 \leq t \leq 10^9$, $1 \leq n, m \leq 3\,000$) --- кількість ковбасок, час з моменту їхнього викрадання та розміри будинку Леді. Далі йдуть $n$ рядків по $m$ символів, опис будинку Леді у форматі, описаному вище.

Можна припустити, що в кімнаті завжди є рівно один холодильник.


\OutputFile

Виведіть одне ціле число - скільки ковбасок може заощадити Леді.

\Note

\begin{center}
\includegraphics{https://static.eolymp.com/content/91/91efc8f53dc347748f4e277d79fa5783.png}
\end{center}

Шлях кота (пунктир) до шафи займе 14 секунд. Коли Леді вибере шлях, позначений суцільною лінією (6 секунд), Леді збереже 6 ковбасок.

\Scoring

За тести без стін всередині будинку можна набрати до 20% балів.