题目描述
AlvinZH儿时有很多梦想,这一次他想开坦克。小时候,他很喜欢看《舒克与贝塔》。
"贝塔贝塔,我是舒克,你的坦克呢?"
"舒克舒克,我是贝塔,我的坦克不见了!"
原来是AlvinZH把贝塔的坦克开走了,秋名山车神上路了。挡在他面前的是一座城市,AlvinZH决定直线冲过去爽爽,但是又怕坦克承受不住,所以需要你帮他设计一条路线。
城市的俯视图如上图,图中的矩形代表建筑物,它们有相同的宽度和不同的长度。AlvinZH在城市南边,"*北漂",请你为他设计一条直线路线,从南到北,必须从城市中穿过,且撞到的建筑物尽可能少。
输入
输入包含多组数据。
每组数据第一行为两个整数n和m,代表城市建筑物的行数和每行的建筑数(0 < n,m ≤ 1000)。
接下来n行,每行m个正整数,代表对应建筑的长度(保证每行建筑长度总和相同,且总长度在int范围内)。
输出
对于每组数据,输出一行,为AlvinZH将会撞到的最小建筑数。
输入样例
3 3
1 2 3
2 1 3
1 3 2
输出样例
1
思路