在一个热闹的水上乐园中,设计师打造了一个 M \times N(1 \leq M, N \leq 500)的矩形泳池区域,每个格子代表一个泳池单元,拥有一个特定的水深值,范围在 0 到 10^9 之间。为了增加乐趣,乐园在某些泳池单元设置了跳水点,作为游客开始入水的起点。
为确保游客的安全和趣味性,乐园需要计算出每个跳水点的趣味值。
每个跳水点的趣味值定义为:满足以下条件的最小整数 C。
请帮助乐园管理者计算所有跳水点的趣味值之和。
第一行包含三个整数 N、M、T,分别表示泳池网格的行数、列数,以及每个跳水点需要访问的最少泳池单元数量。
接下来 N 行,每行包含 M 个整数,表示每个泳池单元的水深值。
再接下来 N 行,每行包含 M 个整数,每个整数为 0 或 1,1 表示该泳池单元是跳水点,0 表示不是。
输出一行一个整数,表示所有跳水点的趣味值之和。
3 5 10 20 21 18 99 5 19 22 20 16 17 18 17 40 60 80 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
24
6 6 15 10 30 50 70 90 110 12 32 52 72 92 112 14 34 54 74 94 114 16 36 56 76 96 116 18 38 58 78 98 118 20 40 60 80 100 120 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
60
8 10 50 100 101 102 103 104 200 201 202 203 204 99 100 101 102 103 199 200 201 202 203 98 99 100 101 102 198 199 200 201 202 97 98 99 100 101 197 198 199 200 201 96 97 98 99 100 196 197 198 199 200 95 96 97 98 99 195 196 197 198 199 94 95 96 97 98 194 195 196 197 198 93 94 95 96 97 193 194 195 196 197 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
288
泳池区域是一个 3 \times 5 的网格,跳水点位于左上角 (1,1) 和右下角 (3,5),每个跳水点需要访问至少 10 个泳池单元。
对于 20\% 的数据,满足 1 \leq N \leq 10,1 \leq M \leq 300,1 \leq T \leq 2000。
对于 100\% 的数据,满足 1 \leq N, M \leq 500,1 \leq T \leq N \times M,每个泳池单元的水深值在 [0, 10^9] 之间,跳水点标记为 0 或 1。