1415 . 水果電廠
TopCoder
Tags
Description
水果可以發電。
現在你有 $n$ 顆水果以及 $b$ 種電極，每一種水果的電極狀態都已經被你事先稽查出來了，第 $i$ 顆水果的電極適配狀態可以用一個長度為 $b$ 的 01 字串表示，第 $i$ 個位置是 1 如果這個水果可以接上一個第 $i$ 種的電極，0 表示不行，每種電極之間互不影響，也就是說，一顆電極狀態是 $\underbrace{111\cdots1}_{b~個}$ 的水果可以插上 $b$ 種電極各一個。
藉由這些水果，你可以蓋一些發電廠。一個發電廠必須使用連續編號的水果，這樣才比較容易蓋廠房，而且一顆水果只可以在一個發電廠當中。因為電極要互相配對，一個發電廠的發電量就是在這個發電廠內可以配對兩個同樣種類電極的最大對數，其中每個電極都只能在一對配對之中。
現在利用你握有的這些資訊，你可以計算最大的發電量是多少嗎？
Input Format
輸入第一行有兩個以一個空白隔開的整數 $n$ 與 $b$，意義如題目所述。
第二行有 $n$ 個以一個空白隔開、長度為 $b$ 的 01 字串 $s_1, s_2, \ldots, s_n$。$s_i$ 代表第 $i$ 顆水果的電極適配狀態。
- $1 \leq n \leq 10^ 5$
- $1 \leq b \leq 64$
Output Format
輸出最大的發電量。
Sample Input 1
7 3 001 010 110 100 001 010 011
Sample Output 1
4
Hints
在範例中，其中一個方法是興建兩座發電廠，涵蓋第 2 至 4 顆與第 5 至 7 顆水果。
兩座發電廠的發電量都是 2，因此總發電量是 4。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 0~10 | 無特別限制。 | 100 |