#2290. 组合数学

组合数学

组合数学

题目描述

NOI 2015天津市代表队选拔赛day1 B 组合数学 • 输入输出文件: math.in/math.out • 源文件名: math.cpp/math.c/math.pas • 时间限制: 2s 内存限制: 128M 题目描述 为了提高智商,ZJY开始学习组合数学。某一天她解决了这样一个问题:“ 给一个网格图,其中某些格子有财宝。每次从左上角出发,只能往右或下走。 问至少要走几次才可能把财宝全捡完。”但是她还不知足,想到了这个问题的 一个变形:假设每个格子中有好多块财宝,而每一次经过一个格子至多只能捡 走一块财宝,其他条件不变,至少要走几次才可能把财宝全捡完? 这次她不会做了,你能帮帮她吗? 输入 第一行为一个正整数t,表示数据组数。 每组数据的第一行是两个正整数n和m,表示这个网格图有n行m列。 接下来n行,每行m个非负整数,表示这个格子中的财宝数量(0表示没有财 宝)。 输出 对于每组数据,输出一个整数,表示至少走的次数。 样例输入 1 3 3 0 1 5 5 0 0 1 0 0 样例输出 10 数据范围 对于30%的数据,n ≤5, m ≤5, 每个格子中的财宝数不超过5块。 对于50%的数据,n ≤100, m ≤100, 每个格子中的财宝数不超过1000块。 对于100%的数据,n ≤1000, m ≤1000, 每个格子中的财宝数不超过106块。 4

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
3 3
0 1 5
5 0 0
1 0 0
10