给你 n 个开关和 m 个灯。第 i 个开关打开部分灯。该信息以由 n 行和 m 列组成的矩阵 a 的形式给出,其中如果第 i 个开关打开第 j 个灯,则 ai, j = 1;如果第 i 个开关未连接到第 j 个灯,则 ai, j = 0。
最初,所有 m 个灯都关闭。
开关仅将状态从“关闭”更改为“打开”。这意味着,如果您按下连接到同一盏灯的两个或多个开关,则在按下任何一个开关后,该灯将打开,并且即使随后按下连接到该灯的任何开关,该灯也会保持其状态。
如果按下所有 n 个开关,则保证所有 m 个灯都会打开。
您认为您有太多开关,并且您想忽略其中一个。
你的任务是判断是否存在这样一个开关,如果你忽略(不使用)它但按下所有其他 n - 1 个开关,那么所有 m 个灯都会打开。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2000) — 开关的数量和灯的数量。
以下 n 行每行包含 m 个字符。如果第i个开关打开第j个灯,则字符ai,j等于“1”,否则等于“0”。
如果按下所有 n 个开关,则保证所有 m 个灯都会打开。
输出
如果有一个开关,则打印“YES”,如果您忽略它并按下所有其他 n - 1 个开关,则所有 m 个灯将打开。如果没有这样的开关,则打印“NO”。
示例
输入 #1
4 5 10101 01000 00111 10000
输出 #1
YES
输入 #2
4 5 10100 01000 00110 00101
输出 #2
NO