/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
N 枚の板があり，それぞれ板 1，板 2，...，板 N と番号づけられております．
板 i の長さは L_i センチメートルであり，左から数えて，j-1 センチメートルから j センチメートルまでの区間は，色 S_{i, j} で塗られております．S_{i, j} = 0 のとき透明，S_{i, j} = 1 のとき赤です．
さて，あなたは N 枚の板を適当な位置に置き，重ねることができます．
「i 枚目の板は，左端が原点から m_i センチメートルの位置に来るように置く」とするとき，各板について，m_i は 0 以上 10 \ 000 以下の整数で決めることができます．
重なっている板を上から見ると，板の赤い部分が 1 枚以上重なっている部分は，赤く見えます．
上から見たときの，連続する「赤く見える部分」の長さの最大が，できるだけ大きくなるような置き方を，一つ求めてください．ただし，最適なものを求める必要はありません．
制約
- N = 300．
- 31 \leq L_i \leq 62．
- S_{i, j} は 0 または 1．
テストケース生成について
テストケースは，以下のステップに基づいて生成されます．
- L_i の値を，31 以上 62 以下の整数の中から，一様ランダムに選ぶ．
- B を，0.15 以上 0.55 以下の一様な確率分布に基づいて決定された，ランダムな値とする．
- 各 j (1 \leq j \leq L_i) について独立に S_{i, j} の値が決められる．確率 B で S_{i, j} = \ 1 となり，確率 1-B で S_{i, j} = \ 0 となる．(23:11 訂正)
- 得られた S_{i, 1}, S_{i, 2}, S_{i, 3}, ..., S_{i, L_i} が全部 0 の場合は，ステップ 1. からやり直す．
得点
提出に対する得点は，以下のように決定されます．
- 採点に使われる 10 個のテストケースのうち，1 つでも条件を満たさない出力（0 \leq m_i \leq 10 \ 000 を満たさない，不正な出力フォーマットなど）があれば，0 点となります．
- そうでない場合，i 個目のテストケースの得点を a_i 点とするとき，提出に対する得点は \frac{a_{1}+a_{2}+a_{3}+...+a_{10}}{10} 点を小数点以下切り捨てた値となります．
なお，各テストケースに対する得点は，以下のようになります．（100 点を超える場合があります．）ただし，連続する「赤く見える部分」の長さの最大を D とします．
- D \leq 199 のとき，5 点．
- 200 \leq D \leq 4 \ 209 のとき，100 - 30log_2(\frac{4810 - D}{600}) 点を小数点以下切り捨てた得点．
- 4 \ 210 \leq D のとき，100 + \frac{D - 4 \ 210}{10} 点．
入力
入力は以下の形式で標準入力から与えられます．
N
s_{1,1}s_{1,2}s_{1,3}...s_{1,L_{1}}
s_{2,1}s_{2,2}s_{2,3}...s_{2,L_{2}}
s_{3,1}s_{3,2}s_{3,3}...s_{3,L_{3}}
:
s_{N,1}s_{N,2}s_{N,3}...s_{N,L_{N}}
出力
以下の形式で出力してください．
m_1 m_2 m_3 : m_N
ただし，m_i は 0 以上 10 \ 000 以下の整数でなければなりません．
入出力例
例えば，以下の入力例を考えましょう．(N, L_i が制約の条件を満たさないため，採点に用いられるデータには含まれません．)3 1101 011 10101
出力例 1
4 7 3
この出力に対応する図は，以下のようになります．
左から数えて，7 センチメートルから 10 センチメートルまでの，長さ 3 センチメートルの区間が，連続して赤く見えます．また，これが最大の長さです．そのため，この出力をした場合のスコアは 5 点となります．
なお，この入力例は，N = 300，31 \leq L_i \leq 62 の条件を満たさないため，テストデータには含まれません．
採点に用いられるすべてのテストケースは，N = 300，31 \leq L_i \leq 62 を満たします．