#P1139. F.再也不想喝香飘飘了

    ID: 154 Type: Default 1000ms 256MiB Tried: 40 Accepted: 17 Difficulty: 5 Uploaded By: Tags>动态规划其他排序SWPUACM周赛

F.再也不想喝香飘飘了

Background

出完P1139的Zoey学姐心力交瘁,题面和数据一直出问题,她不想再看到香飘飘三个字了

Description

现在Zoey学姐要回家,走到一个n*m的矩阵前,入口是最左上角,出口是最右下角,由于学姐太过疲惫,她只想向下或向右走(方向是相对于整个矩阵),矩阵的每一小格内有x个香飘飘,每走过一个小格Zoey都必须拿走格内的香飘飘,已知矩阵情况,请你帮Zoey算出她最少可以拿多少杯香飘飘离开矩阵。

Format

Input

第一行输入一个正整数T代表有T组数据(0≤T≤10),接下来有T组数据 对于每组数据,第一行输入两个正整数n 和m(n为行数m为列数)接下来是n行数据,每行数据有m个x,且x为整型,为每个格子内香飘飘数(0≤n,m,x<=100)。

Output

对于每组数据输出一个整数,为Zoey学姐最少带走的香飘飘数。

Samples

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

Limitation

1s, 1024KiB for each test case.