/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
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お姉ちゃんの店の利益のあり得る最大値を求めてください。
制約
- 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
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 1 0 1 0 0 0 1 0 1 3 4 5 6 7 8 9 -2 -3 4 -2
出力例 1
8
店 1 が営業している時間帯のみに店を営業すると、利益 8 を得ることができ、利益が最大となります。
入力例 2
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
-2
1 つ以上の時間帯で店を営業しなければならないことや、利益が負となる場合があることに注意してください。
入力例 3
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
出力例 3
23
Score : 300 points
Problem Statement
Joisino is planning to open a shop in a shopping street.
Each of the five weekdays is divided into two periods, the morning and the evening. For each of those ten periods, a shop must be either open during the whole period, or closed during the whole period. Naturally, a shop must be open during at least one of those periods.
There are already N stores in the street, numbered 1 through N.
You are given information of the business hours of those shops, F_{i,j,k}. If F_{i,j,k}=1, Shop i is open during Period k on Day j (this notation is explained below); if F_{i,j,k}=0, Shop i is closed during that period. Here, the days of the week are denoted as follows. Monday: Day 1, Tuesday: Day 2, Wednesday: Day 3, Thursday: Day 4, Friday: Day 5. Also, the morning is denoted as Period 1, and the afternoon is denoted as Period 2.
Let c_i be the number of periods during which both Shop i and Joisino's shop are open. Then, the profit of Joisino's shop will be P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}.
Find the maximum possible profit of Joisino's shop when she decides whether her shop is open during each period, making sure that it is open during at least one period.
Constraints
- 1≤N≤100
- 0≤F_{i,j,k}≤1
- For every integer i such that 1≤i≤N, there exists at least one pair (j,k) such that F_{i,j,k}=1.
- -10^7≤P_{i,j}≤10^7
- All input values are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the maximum possible profit of Joisino's shop.
Sample Input 1
1 1 1 0 1 0 0 0 1 0 1 3 4 5 6 7 8 9 -2 -3 4 -2
Sample Output 1
8
If her shop is open only during the periods when Shop 1 is opened, the profit will be 8, which is the maximum possible profit.
Sample Input 2
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
Sample Output 2
-2
Note that a shop must be open during at least one period, and the profit may be negative.
Sample Input 3
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
Sample Output 3
23