← 返回题目列表

Codeforces · 120/D

D. 三个儿子

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

三个儿子从父亲那里继承了一个长方形的玉米恶魔,分为 n × m 的正方形。对于每个方格,我们知道上面种植了多少吨玉米。父亲是一位老农民,他对三个儿子的爱并不平等,因此他遗赠了他的田地分成三部分,分别有 A、B、C 吨玉米。

场地应被两条平行线分开。这些线应该平行于场地的一侧并且彼此平行。线条应严格位于场地的方格之间。字段的每个结果部分应至少由一个正方形组成。

你的任务是找到如上所述的划分田地的方法的数量,即标记两条线,将田地分成三部分,使得其中一个部分长出 A 吨玉米,另一部分长出 B 吨玉米,剩下的部分长出 C 吨玉米。

输入

第一行包含空格分隔的整数 n 和 m — 原始大小 (1 ≤ n, m ≤ 50, max(n, m) ≥ 3)。那么该字段的描述如下:n 行,每行包含 m 个空格分隔的整数 cij,(0 ≤ cij ≤ 100) — 每个方格包含的玉米吨数。最后一行包含空格分隔的整数 A、B、C (0 ≤ A、B、C ≤ 106)。

输出

打印问题的答案:划分父亲的田地的方式有多少种,使所得的一部分含有 A 吨玉米,另一部分含有 B 吨玉米,剩下的一份含有 C 吨玉米。如果不存在这样的方式,则打印 0。

示例

输入 #1

3 3
1 1 1
1 1 1
1 1 1
3 3 3

输出 #1

2

输入 #2

2 5
1 1 1 1 1
2 2 2 2 2
3 6 6

输出 #2

3

输入 #3

3 3
1 2 3
3 1 2
2 3 1
5 6 7

输出 #3

0

注意

划分场地的线可以是水平的或垂直的,但它们应该彼此平行。