SP27369 SHUB1307 - Gupta ji Birthday !!

# Shubham Gupta的生日！！ 七月十三日是Shubham Gupta的生日。Shubham喜欢解决dp问题。 Anuj（Shubham的朋友）希望他能独一无二。因此，他装饰了他们的235号宿舍房间，房间的地板被 nxm 的方形瓷砖分割，形成了一个由 n行 和 m列 组成的网格。 网格中的每个正方形都包含了一些伏特加，如果Shubham踩到一块特定的瓷砖，他就得喝这些伏特加。Shubham在（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”（不含引号）。 在不同行中打印每个测试用的答案。