AT_abc080_c [ABC080C] Shopping Street

[problemUrl]: https://atcoder.jp/contests/abc080/tasks/abc080_c joisinoお姉ちゃんは、ある商店街に店を開こうとしています。 その商店街の店は、月曜日から金曜日の $ 5 $ つの曜日を午前と午後の $ 2 $ つの時間帯に分けて、これら $ 10 $ 個の時間帯それぞれについて店を営業するか否かを決めることとなっています。ただし、$ 1 $ つ以上の時間帯で店を営業しなければなりません。 商店街には既に $ N $ 個の店があり、$ 1 $ から $ N $ までの番号がついています。 これらの店の営業時間の情報として $ F_{i,j,k} $ が与えられ、月曜日 $ = $ 曜日 $ 1 $、火曜日 $ = $ 曜日 $ 2 $、水曜日 $ = $ 曜日 $ 3 $、木曜日 $ = $ 曜日 $ 4 $、金曜日 $ = $ 曜日 $ 5 $、 午前 $ = $ 時間帯 $ 1 $、午後 $ = $ 時間帯 $ 2 $ と対応させたとき、$ F_{i,j,k}=1 $ なら曜日 $ j $ の時間帯 $ k $ に店 $ i $ が営業しており、$ F_{i,j,k}=0 $ なら営業していないことを意味します。 店 $ i $ とjoisinoお姉ちゃんの開く店の両方が営業している時間帯の個数を $ c_i $ としたとき、joisinoお姉ちゃんの店の利益は $ P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N} $ となります。ただし、利益は負にもなりうることに注意してください。 $ 1 $ つ以上の時間帯で店を営業しなければならないことに注意しつつ、$ 10 $ 個の時間帯それぞれについて店を営業するか否かを決めるとき、joisinoお姉ちゃんの店の利益のあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ F_{1,1,1} $ $ F_{1,1,2} $ $ ... $ $ F_{1,5,1} $ $ F_{1,5,2} $ $ : $ $ F_{N,1,1} $ $ F_{N,1,2} $ $ ... $ $ F_{N,5,1} $ $ F_{N,5,2} $ $ P_{1,0} $ $ ... $ $ P_{1,10} $ $ : $ $ P_{N,0} $ $ ... $ $ P_{N,10} $

joisinoお姉ちゃんの店の利益のあり得る最大値が $ x $ のとき、$ x $ を出力せよ。

### 制約 - $ 1≦N≦100 $ - $ 0≦F_{i,j,k}≦1 $ - $ 1≦i≦N $ を満たす全ての整数 $ i $ に対して、$ F_{i,j,k}=1 $ を満たす $ (j,k) $ が必ず $ 1 $ つ以上存在する - $ -10^7≦P_{i,j}≦10^7 $ - 入力は全て整数 ### Sample Explanation 1 店 $ 1 $ が営業している時間帯のみに店を営業すると、利益 $ 8 $ を得ることができ、利益が最大となります。 ### Sample Explanation 2 $ 1 $ つ以上の時間帯で店を営業しなければならないことや、利益が負となる場合があることに注意してください。