特别简单,适合初学者 ^_^

某天，Lan走到了一个有n*m个方格的迷宫

他发现路上有些星琼金币。

他要在num步内拿到最多的金币抽解斑, 并走到出口。

Damn是，路上有些陷阱（表示为'.'）,如果碰到它，Lan会失去3个金币

请你帮助他吧！

('+'为出口，'?'为Lan所在的位置，保证Lan所在的位置在右上角，出口在左下角不然十分麻烦)

提示

只能往上下左右方向走，可以重复走，但是走到已经走过的位置不会重复算金币的数量，初始金币数量为0

范围

$0\leq n,m\leq 10,保证金币数量不超过int类型范围$

输出

一个整数，表示金币的数量

样例

5 5 8
? 9 4 . 5
. . 4 5 3
1 2 6 5 1
1 8 3 20 2
0 9 4 2 +

44

数据限制

1秒，256MB