#P1139. F.再也不想喝香飘飘了
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.
Related
In following contests: