分数: 300 点
问题陈述
Joisino 计划在商业街开设一家商店。
五个工作日中的每一天都分为两个时段,早上和晚上。对于这十个时段中的每个时段,商店必须在整个时段内营业或在整个时段内关闭。当然,商店必须至少在其中一个时段营业。
已经有 N 街上的商店,编号 1 通过 N.
您将获得这些商店的营业时间信息, F_{i,j,k}。如果 F_{i,j,k}=1, 商店 i 期间开放 k 当天 j (此符号解释如下);如果 F_{i,j,k}=0, 商店 i 在此期间关闭。这里,一周中的几天表示如下。周一:白天 1,星期二:白天 2,星期三:白天 3,星期四:白天 4,星期五:白天 5。此外,早上也表示为“期间” 1,下午表示为期间 2.
让 c_i 是双方都购物的时间段数 i 和Joisino的商店已营业。那么,Joisino 店铺的利润为 P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}.
求 Joisino 的店铺在决定其店铺在每个时段是否营业时的最大可能利润,并确保该店铺至少在一个时段内营业。
约束
- 1≤N≤100
- 0≤F_{i,j,k}≤1
- 对于每个整数 i 这样 1≤i≤N,至少存在一对 (j,k) 这样 F_{i,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店铺的最大可能利润。
示例输入 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
请注意,一家商店必须至少在一个时期内营业,并且利润可能为负数。
示例输入 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