你们的大学确实需要一栋专门用于计算机科学的新大楼。系里有足够的资金，但市议会不愿批准该大楼的建筑许可。这太不幸了！

幸运的是，议会选举即将来临。你决定以“计算机科学利益委员会党”（ICPC）的名义参加选举。一旦你在议会中获得多数席位，你和你的同事们就可以批准建造新大楼。

议会选举在若干个选区举行，选民被分配到这些选区中。每个选区选出一名议员。每个政党在每个选区派出一名候选人，每位选民只有一票。在每个选区中获得票数最多的候选人将当选为议员。

由于新大楼对你和你的同事们非常重要，你们不想冒任何风险。如果议会中出现平局，或者在某个选区的选举中出现无人知晓结果的情况，后果难以预料。因此，你们的目标是在议会中获得绝对多数席位，即超过半数的席位。此外，在你们认为获胜的每个选区中，ICPC 候选人必须获得严格多于其他任何候选人的票数。

你和你的 ICPC 同事们已经创建了一个极其复杂的选举模拟系统。因此，你们确切地知道每个选区中每个候选人将获得的票数。遗憾的是，你们的模型并未预测到 ICPC 会在选举中获胜。现在面临一个棘手的问题：为了赢得选举，你至少需要贿赂多少名选民？如果你贿赂了一名选民，他会将之前支持的政党（根据你们的精确建模，你们已知其原本支持的政党）改为支持 ICPC。那些原本不打算投票的人无法被贿赂。

输入格式

输入包含： 一行包含两个整数 $w$ 和 $p$ ($2 \le w, p \le 1\,000$)，分别表示选区数量和参加选举的政党数量。政党编号为 $1$ 到 $p$，其中 ICPC 为第 $1$ 党。 $w$ 行，每行包含 $p$ 个整数 $v_1, \dots, v_p$ ($0 \le v_i \le 1\,000$，对于每个 $i$)，给出了一个选区的预计结果。$v_i$ 表示将投给第 $i$ 个政党的票数。

保证每个选区至少有一名选民，即每个选区中所有 $v_i$ 的总和至少为 $1$。

输出格式

输出为了让 ICPC 赢得议会多数席位而必须贿赂的最少选民人数。

样例

输入 1

3 3
0 2 2
1 2 3
0 2 3

输出 1

4

输入 2

2 4
0 1 2 9
1 0 0 0

输出 2

5

输入 3

3 3
1 0 0
0 1000 0
0 9 5

输出 3

6