Problem Description

小Q最近迷上了一款寻宝游戏，这款游戏中每局都会生成一个$n\times m$的网格地图，从上往下依次编号为第$1$行到第$n$行，从左往右依次编号为第$1$列到第$m$列。每个格子上都有不同数量的金币，第$i$行第$j$列的格子上的金币数量为$a_{i,j}$。

小Q一开始位于$(1,1)$，每次他可以往右或者往下走，每当他经过某个格子时，他就可以拿走这个格子上的所有金币。小Q不能走出这个地图，当小Q不能再行动时，游戏结束。显然当且仅当小Q位于$(n,m)$时，游戏才会结束。

一轮游戏的得分为这一轮中收集到的金币总量，而在游戏开始前，因为小Q是超级VIP用户，所以他有$k$次机会交换某两个格子中的金币数。这$k$次机会不一定要用完，请写一个程序帮助小Q在一轮内拿到尽可能多的金币。

Input

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含三个整数$n,m,k(2\leq n,m\leq 50,0\leq k\leq 20)$，分别表示地图的长宽以及交换的次数。

接下来$n$行，每行$m$个整数$a_{i,j}(0\leq a_{i,j}\leq 10^6)$，依次表示每个格子中金币的数量。

Output

对于每组数据，输出一行一个整数，即能收集到的金币数量的最大可能值。

2
3 4 0
1 2 3 4
9 8 7 6
5 4 7 2
5 5 1
9 9 9 0 0
0 0 9 0 0
0 0 0 0 0
0 0 9 0 0
9 0 9 9 9

34
81