题目描述

DZY 家的后院有一块地，由 $n$ 行 $m$ 列的方格组成，格子内种的菜有一定的价值，并且每一条单位长度的格线有一定的费用。

DZY 喜欢在地里散步。他总是从任意一个格点出发，沿着格线行走直到回到出发点，且在行走途中不允许与已走过的路线有任何相交或触碰（出发点除外）。记这条封闭路线内部的格子总价值为 $v$，路线上的费用总和为 $c$，DZY 想知道 $\dfrac{v}{c}$ 的最大值是多少。

输入格式

第一行为两个正整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个非负整数，表示对应格子的价值。

接下来 $n+1$ 行，每行 $m$ 个正整数，表示所有横向的格线上的费用。

接下来 $n$ 行，每行 $m+1$ 个正整数，表示所有纵向的格线上的费用。

（所有数据均按从左到右，从上到下的顺序输入，参见样例和配图）

输出格式

输出一行仅含一个数，表示最大的 $\dfrac{v}{c}$，保留 $3$ 位小数。

3 4
1 3 3 3
1 3 1 1
3 3 1 0
100 1 1 1
97 96 1 1
1 93 92 92
1 1 90 90
98 1 99 99 1
95 1 1 1 94
1 91 1 1 89

1.286

提示

数据规模与约定

• 对于 $100\%$ 的数据，$n,m \leq 50$，$0 \leq \text{价值} \leq 100$，$1 \leq \text{费用} \leq 100$。

题目来源

jcvb 提供