Background

在并不美好的一天，抠鼻打开了猴瓶精英的地铁逃生，穿上四级套当起了老鼠。 老鼠的运气并不是完全的好。 在地下迷宫区，有一个$h\times w$大小的迷宫（起点在左上角）。 迷宫中有“数得尽”的财宝（$1\sim 3$分别代表越来越高级的财宝），抠鼻有$n$步，需要尽量拿到价值高的财宝（不需要考虑返回）。

输出抠鼻获得的最大价值。

Description

输入$n，h，w$ 随后一个$h\times w$的迷宫

Format

Input

三个整数$n，h，w$ 一个$h\times w$字符数组

Output

一个数字，抠鼻的最大价值

Samples

1 5 5
* * * * *
* * * * *
* *2 3 *
* * * * *
* * * * *

0

Limitation

1s, 1024KiB for each test case.