解题思路
格子 (i,j) 的能量值为 i⋅m+j。向下走一行能量增加 m，向右走一列只增加 1。因此应优先向下走到最底行，再向右走到最右列；若还有剩余步数，在能量最高的相邻两格之间往返。
具体计算：
- 若 k≥n−1，先沿第一列走到 (n−1,0)，收集等差数列 m,2m,…,(n−1)m；否则只走 k 步向下。
- 剩余步数再沿底行向右，收集 (n−1)m+1,(n−1)m+2,…。
- 若仍有余步：当 m=1 时在底行最右两格往返；当 m=1 时在最底两行之间往返。奇数步取较小的那格，偶数步取较大的那格。
题目内容
科创园区地面铺设了 n 行 m 列能量板，左上角为 (0,0)，右下角为 (n−1,m−1)。格子 (i,j) 的能量值为 i×m+j。巡逻机器人从 (0,0) 出发，每步可以走到上下左右四个方向的相邻格子。每到达一格就收集该格当前能量；离开后再进入时能量会重新刷新，可以再次收集。调度系统给出 q 组询问，每组给出网格规模与步数上限 k，求最多走 k 步能收集到的能量总和。起点 (0,0) 的能量为 0。
约束：1≤q≤100000，1≤n,m,k≤10000，且 n+m>2。
输入描述
第一行一个整数 q，表示询问个数。
接下来 q 行，每行三个整数 n、m、k，表示网格规模与步数上限。
