A1-2017级算法上机第一次练习赛 M AlvinZH的儿时梦想——坦克篇

时间:2022-02-27 12:53:36

题目描述

AlvinZH儿时有很多梦想,这一次他想开坦克。小时候,他很喜欢看《舒克与贝塔》。

"贝塔贝塔,我是舒克,你的坦克呢?"

"舒克舒克,我是贝塔,我的坦克不见了!"

原来是AlvinZH把贝塔的坦克开走了,秋名山车神上路了。挡在他面前的是一座城市,AlvinZH决定直线冲过去爽爽,但是又怕坦克承受不住,所以需要你帮他设计一条路线。

A1-2017级算法上机第一次练习赛 M AlvinZH的儿时梦想——坦克篇

城市的俯视图如上图,图中的矩形代表建筑物,它们有相同的宽度和不同的长度。AlvinZH在城市南边,"*北漂",请你为他设计一条直线路线,从南到北,必须从城市中穿过,且撞到的建筑物尽可能少。

输入

输入包含多组数据。

每组数据第一行为两个整数nm,代表城市建筑物的行数和每行的建筑数(0 n,m ≤ 1000)。

接下来n行,每行m个正整数,代表对应建筑的长度(保证每行建筑长度总和相同,且总长度在int范围内)。

输出

对于每组数据,输出一行,为AlvinZH将会撞到的最小建筑数。

输入样例

3 3

1 2 3

2 1 3

1 3 2

输出样例

1

思路