U453589 Uim的生日

七月十三日是Uim的生日。Uim喜欢解决dp问题。

小A（Uim的朋友）希望他能独一无二。因此，他装饰了他们的114号宿舍房间， 房间的地板被 nxm 的方形瓷砖分割，形成了一个由 _n_ 行和 _m_ 列组成的网格。 网格中的每个正方形都包含了一些伏特加，如果Uim踩到一块特定的瓷砖，他就得喝这些伏特加。 Uim在（1,1）上进入房间，并不得不向出口大门（在(n,m)上）走去，途中喝下伏特加。从当前单元格开始， 他只能向东、南或东南方向的相邻单元格移动，即从(I，J)到(I，J+1)、(I+1，J)或（(I+1)，J+1）。 然而，他的伏特加酒量是有限的。如果他喝的伏特加超过k，他会失控的！帮助他尽可能多地喝酒，但不要失去控制。

第一行包含一个数T。其后为T个测试用例。 每个测试用例的第一行包含3个以空格分隔的整数，n,m,k。 以下n行中的每一行都包含m个以空格分隔的整数，描述网格。

打印出他在不失控的情况下可以饮用的伏特加的最高数量。 如果不能这样做，即不存在符合要求的路径，则输出“-1”（不含引号）。 在不同行中打印每个测试用的答案。

0 < T,n,m,k < 514