Вам задана карта — прямоугольная таблица. Каждая клетка таблицы — это: либо препятствие, либо сокровище с определенной стоимостью, либо бомба, либо пустая клетка. Также задано ваше начальное положение.

Вы можете перейти из клетки в соседнюю по стороне клетку карты. При этом не разрешается выходить за пределы карты, приходить в клетки с сокровищами, препятствиями и бомбами. Для того, чтобы собрать сокровища, вы должны построить замкнутый путь (он должен начинаться и заканчиваться в стартовой клетке). Внутри этого замкнутого пути не должно быть клеток с бомбами. Пусть сумма стоимости сокровищ, находящихся внутри замкнутого пути, равна v, и при этом вы совершили k единичных переходов (из клетки в клетку), когда проходили этот путь, тогда такой путь принесет вам прибыль v - k рублей.

Ваша задача построить замкнутый путь, внутри которого не содержится бомб, который принесет наибольшую прибыль.

Обратите внимание, что путь может иметь самопересечения. Для определения того, лежит клетка внутри пути или нет используется следующий алгоритм:

1. Представьте себе, что клетки таблицы — это точки на плоскости (клетка таблицы на пересечении i-го столбца и j-ой строки является точкой (i, j)). А заданный вам путь — это замкнутая ломаная, проходящая через эти точки.
2. Вам нужно определить: находится ли точка p таблицы, через которую не проходит ломаная, внутри ломаной.
3. Проведем луч, начинающийся в точке p и не проходящий через другие точки таблицы (такой луч обязательно существует).
4. Посчитаем сколько отрезков ломаной пересекает проведенный луч. Если это количество нечетно, считается, что точка p (а следовательно и клетка таблицы) находится внутри ломаной (пути). Иначе, считается, что она находится снаружи.