U389089 稀世珍宝

 > 萝卜头：熊大你这个缺心眼，给了猴子那么多宝石，还骗我说是什么稀世珍宝，我要和你绝交!

萝卜头听了熊大的话，去了一个山洞找稀世珍宝，熊大给了萝卜头一张地图，为 $n \ \times \ m$ 的矩阵，其中`.`代表空洞，需要 1 秒通过，`|`代表死路，但由于萝卜头会挖洞，它可以用 2 秒钟挖开并通过，`$`代表稀世珍宝，萝卜头可以将它收起来，`&`代表死路中藏着稀世珍宝，可以以 3 秒挖开并收下稀世珍宝。 入口在 $a_{[1][1]}$ 的位置，出口在 $a_{[n][m]}$ 的位置，萝卜头只可以上下左右移动。 但萝卜头提前知道山洞会在 $t$ 秒内坍塌，需要在 $t$ 秒内逃出山洞。

第一行输入三个正整数 $n,m,t(2\le n, m \le 10^{3},\ 3 \le t \le 10^{6})$。 接下来输入 n 行 m 列的矩阵，表示熊大给萝卜头的地图。

一行，在 $t$ 秒内逃出山洞所获得最多的稀世珍宝数量，如果不能逃出山洞，输出`NO`。

对于 $100\%$ 的数据，保证 $2\le n \le 10^{3}$，$2\le n \le 10^{3}$，$\ 3 \le t \le 10^{6}$