TopCoder

Thumb vqv4lsq
icube
baluteshih 好強 <(_ _)>

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

19.6% (11/56)

Tags

Description

你所管理的蕃茄小豆湯工廠最近出了點問題。因為年久失修,有一些用來裝填蕃茄小豆湯罐頭的機器故障了。

蕃茄小豆湯的生產線是這樣的: 首先,空的罐頭會先被放入紙箱中排好,然後讓整個紙箱進入生產線通過若干部機器,因為有些機器是故障的(可能是噴嘴塞住了)所以只能裝填部分的罐頭,所以需藉由數部機器的合作來完成裝填。然而已被裝填的罐頭就不能再被裝填,否則蕃茄小豆湯就會滿出來流得到處都是。

你的任務是找出最少需要多少部機器,才能完成可以裝滿每一個罐頭的生產線。

Input Format

輸入的第一行有兩個正整數N,M (N,M≤200),表示有N台機器,M個罐頭要裝。

接下來有N行,每行有M個數為0或1,第i個數為0表示無法裝填第i個罐頭;為1表示可以裝填第i個罐頭。

Output Format

輸出最少需要幾部機器。

Sample Input

5 6
0 1 1 0 1 1
1 1 0 1 0 0
0 0 1 0 0 1
1 1 0 1 0 1
0 0 0 0 1 0

Sample Output

3

Hints

選擇第2,3,5部機器

Problem Source

原TIOJ1333 / Problem Setter:seanwu

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7