题目背景

学校社团节设置了 $n$ 个打卡点，一共有 $m$ 个不同的体验项目。每个打卡点会提供其中若干个项目，参加活动的同学希望尽量少跑几个打卡点，就能体验到全部项目。

题目描述

接下来给出 $n$ 个长度为 $m$ 的字符串。第 $i$ 个字符串的第 $j$ 个字符为 1，表示第 $i$ 个打卡点提供第 $j$ 个项目；为 0，表示不提供。

保证每个打卡点至少提供一个项目，每个项目也至少会被某个打卡点提供。

请计算最少需要选择多少个打卡点，才能覆盖所有 $m$ 个项目。

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示打卡点数量和项目数量。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只包含 0 和 1。

输出格式

输出一个整数，表示覆盖所有项目所需的最少打卡点数量。

样例

3 5
11100
01110
00111

2

3 2
11
10
01

1

8 6
001001
001000
010000
000100
001111
000010
010010
101001

3

提示

样例解释

样例 $1$ 中，选择第 $1$ 个和第 $3$ 个打卡点，就能覆盖全部 $5$ 个项目，且无法只选一个打卡点完成。

数据范围

对于 $100\%$ 的数据，$1 \le m,n \le 20$。