Задача D. Городские стены

"Вот открыл царевич очи;
Отрясая грезы ночи
И дивясь, перед собой
Видит город он большой,
Стены с частыми зубцами..."

Когда Царевна-Лебедь проектировала город для будущего князя Гвидона, она хотела, чтобы дворец князя находился в центре города, а весь город был бы огражден высокой каменной стеной.
Остров может быть описан совокупностью квадратов (задается картой), причем гарантируется, что если какие-либо два квадрата принадлежат острову, то между ними существует путь, не требующий ни одного перехода через угол квадрата.
Карта острова задается на прямоугольной сетке размера N x M. Квадраты, помеченные как X, являются частью острова, помеченные как . - относятся к морю. Сторону квадрата считайте равной 1. Квадрат, в котором содержится дворец, помечен буквой D.

Царевна решила, что:
1) стеной должны быть огорожены квадраты, центр которых удален от дворца не более, чем на R единиц (центр квадрата, в котором находится дворец, следует считать центром окружности радиуса R)
2) если такие квадраты оказываются за пределами острова, то стена строится по береговой линии
3) стена должна быть непрерывной, и из любого квадрата внутри ограждения существует путь до любого другого квадрата внутри ограждения, не требующий ни одного перехода через угол квадрата.

По заданной карте острова определите, какова будет длина построенной стены.

Формат входного файла input.txt
Первая строка - целые числа N, M, R (0 < N, M, R <= 1000)
Следующие N строк содержат по M символов в строке (пробелов между символами нет) согласно описанию задачи

Формат выходного файла output.txt
Первая строка - целое число - длина стены вокруг города

Пример входного файла
8 12 3
............
...XXXXXX...
...X...XX...
.XXD...XX...
.XXXX.......
....XXXX....
...XX.XX....
............

Пример выходного файла
24