小华按照地图去寻宝，地图上被划分成 n n n 行和 m m m 列的方格，横纵坐标范围分别是 [ 0 , n − 1 ] [0, n-1] [0,n−1] 和 [ 0 , m − 1 ] [0, m-1] [0,m−1]。

在横坐标和纵坐标的数位之和不大于 k k k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标数位之和大于 k k k 的方格存在危险不可进入。小华从入口 ( 0 , 0 ) (0,0) (0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。

请问小华最多能获得多少克黄金？

坐标取值范围如下：

0 ≤ m ≤ 5 0 ≤ m ≤ 5 0≤m≤5

0 ≤ n ≤ 5 0 ≤ n ≤ 5 0≤n≤5

k k k 的取值范围如下：

0 ≤ k ≤ 10 0 ≤ k ≤ 10 0≤k≤10

输入中包含 3 个字数，分别是 m, n, k

输出小华最多能获得多少克黄金

本题的重点在于理解数位和的概念。

所谓数位和，指的是一个正整数的各个位的和。比如11的数位和是1+1 = 2

对于任意一个正整数n，其数位和可以通过以下两种方式任选其一进行计算。在效率上，数学方法略优于字符串方法，但因为数据量不大，所以都可以使用。

在拿到地图的大小n*m之后，就可以通过双重循环遍历的方式，构建出每一个位置的数位和矩阵grid。

拿到数位和矩阵grid之后，由于小华从起点出发上下左右均可以移动，所以问题就转化为了从起点(0, 0)开始进行图的索能够到达多大面积的地图。

这个问题用DFS或者BFS都可以完成。直接套模板即可。