题目描述

现在有一大块土地,可以看成 n×mn\times m 的方格。在这块土地上,有些格子内是崎岖的山地,无法建造任何东西;其他格子都是平原。现在打算在这块土地上建设一个游乐园。游乐园由若干条闭合的过山车轨道组成,每个平原格子都要铺一截轨道,为下列 66 种类型中的一种(每张图表示一块平原格子,图内网格线为辅助线,无实际意义) :其中前 22 种为直轨道,后 44 种为弯轨道。

轨道

显然对游客来说,弯轨道更加刺激。 由于每块格子风景各不相同,经过一番研究,现给了 n×mn\times m 个方格中的每个格子一个评估值,意义为:如果该格子修建弯轨道,会给游客们带来多少的愉悦值。现需要一名设计师,帮他设计一种最优的轨道建设方案,使所有格子给游客们带来的愉悦值之和尽量大。(如果没有合法方案,输出 1-1

输入格式

第一行两个正整数 n,mn, m。 接下来 nn 行,每行 mm 个数,描述了整块土地。其中 11 表示山地,00 表示平原。
接下来 nn 行,每行 mm 个非负整数,第 ii 行第 jj 个为 Vi,jV_{i,j},表示格子 (i,j)(i,j) 修建弯轨道能给游客们带来的愉悦值。

输出格式

一行一个数,表示最优设计方案中给游客们带来的愉悦值之和。

输入数据 1

3 3
1 1 1 
1 0 0 
1 0 0 
48 94 1 
78 78 81 
1 12 60

输出数据 1

231

提示

n150,m30,Vi,j100n\le150,m\le30,V_{i,j}\le100

1 comments

  • 1

Information

ID
4261
Time
1000ms
Memory
256MiB
Difficulty
8
Tags
(None)
# Submissions
32
Accepted
7
Uploaded By