← 返回题目列表

AtCoder · abc080_c

C. 商店街

中文机器翻译题面 查看原题

分数: 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