[ABC080C] Shopping Street

## 题目描述 Joisino计划要在商店街开一家店。 这家店在周一到周五的$5$ 个工作日都有营业，其中每个工作日又被划分成上午和下午$2$ 个时间段，也就是共有$10$ 个时间段。当然，至少要有$1$ 个时间段这家店营业。 商店街原来有$N$ 个店铺，从$1$ 到$N$ 编号。 这些店铺的营业时间将以$F_{i,j,k}=1$ 的形式给出。如果$F_{i,j,k}=1$ ，第$i$ 家店将在第$j$ 天的第$k$ 个时间段营业。在这里，我们这样定义：第$1$ 天是周一，第$2$ 天是周二，第$3$ 天是周三，第$4$ 天是周四，第$5$ 天是周五。同样的，第$1$ 个时间段是上午，第$2$ 个时间段是下午。 设$c_i$ 为第$i$ 家店和Joisino的店同时营业的时间段数，则Joisino商店的收益将会是$P_{1,c1}+P_{2,c2}+...+P_{N,cN}$ 。 请决定Joisino在这$10$ 个时间段分别是否营业，并求出Joisino商店可能的最大收益，且保证它至少要有$1$ 个时间段营业。 ## 输入输出格式 ### 输入格式 第一行，一个整数$N$ 。 接下来$N$ 行，第i行有10个整数，分别表示$F_{i,1,1}, F_{i,1,2}, ..., F_{i,5,1}, F_{i,5,2}$ 。 再接下来$N$ 行，第i行有11个整数，分别表示$P_{i,0}, ..., P_{i, 10}$ 。 ### 输出格式 只有一行，一个整数，表示Joisino商店可能的最大收益。 ## 说明 ### 样例解释1 如果商店仅在第$1$ 家店营业时营业，收益将会是$8$ ，这是可能的最大收益。 ### 样例解释2 由于必须至少有一个时间段商店营业，所以收益可能会是负数。 ### 数据范围 - $1 \leq N \leq 100$ - $0 \leq F_{i,j,k} \leq 1$ - 对所有满足 $1 \leq i \leq N$ 的 $i$ , 总有一对$(j, k)$ 满足$F_{i,j,k}=1$ 。 - $-10^7 \leq P_{i,j} \leq 10^7$ - 所有输入数据均为整数。 by @月见之兔

[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
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2

8

2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1

-2

3
1 1 1 1 1 1 0 0 1 1
0 1 0 1 1 1 1 0 1 0
1 0 1 1 0 1 0 1 0 1
-8 6 -2 -8 -8 4 8 7 -6 2 2
-9 2 0 1 7 -5 0 -2 -6 5 5
6 -6 7 -9 6 -5 8 0 -9 -7 -7

23

### 制約 - $ 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 $ つ以上の時間帯で店を営業しなければならないことや、利益が負となる場合があることに注意してください。