F. Цивилизация: только время

Та же карта из поля, леса и воды, те же правила: поле стоит единицу, лес — двойку, вода непроходима. Но маршрут выводить не надо — только наименьшее время.

Зато карта больше: до тысячи на тысячу.

Первая строка содержит числа $N$ и $M$ ($1 \le N, M \le 1000$), затем координаты начальной и конечной клетки.

Далее идут $N$ строк по $M$ символов ., W, #.

Одно число — наименьшее время или $-1$.