Three Sons

题意翻译

**题意简述** 给定一个 $n\times m$ 的长方形矩阵，第 $(i,j)$ 个方格上面有一个值 $c_{i,j}$。现在要将矩阵分成三部分，要求两条切割线必须互相平行且与边线平行，不能切开网格，使得切出的三部分每个部分所包含的方格的值的总和分别为 $A$，$B$，$C$。求有多少种切法。 **输入格式** 第一行包含两个整数 $n,m$（$1\le n,m\le 50$，$\max(n,m)\ge 3$）。 接下来 $n$ 行，每行包含 $m$ 个整数 $c_{i,j}$（$0\le c_{i,j}\le 100$），表示矩阵中 $(i,j)$ 的值。 第 $n+2$ 行包含三个整数 $A,B,C$（$0\le A,B,C\le 10^6$），意义如上所示。 **输出格式** 输出一行表示答案。如无解请输出 $0$。 **样例 $1$ 说明** 对于该样例，可横着切亦可竖着切，如图： 

题目描述

Three sons inherited from their father a rectangular corn fiend divided into $ n×m $ squares. For each square we know how many tons of corn grows on it. The father, an old farmer did not love all three sons equally, which is why he bequeathed to divide his field into three parts containing $ A $ , $ B $ and $ C $ tons of corn. The field should be divided by two parallel lines. The lines should be parallel to one side of the field and to each other. The lines should go strictly between the squares of the field. Each resulting part of the field should consist of at least one square. Your task is to find the number of ways to divide the field as is described above, that is, to mark two lines, dividing the field in three parts so that on one of the resulting parts grew $ A $ tons of corn, $ B $ on another one and $ C $ on the remaining one.

输入输出格式

输入格式

The first line contains space-separated integers $ n $ and $ m $ — the sizes of the original ( $ 1<=n,m<=50,max(n,m)>=3 $ ). Then the field's description follows: $ n $ lines, each containing $ m $ space-separated integers $ c_{ij} $ , ( $ 0<=c_{ij}<=100 $ ) — the number of tons of corn each square contains. The last line contains space-separated integers $ A,B,C $ ( $ 0<=A,B,C<=10^{6} $ ).

输出格式

Print the answer to the problem: the number of ways to divide the father's field so that one of the resulting parts contained $ A $ tons of corn, another one contained $ B $ tons, and the remaining one contained $ C $ tons. If no such way exists, print 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

说明

The lines dividing the field can be horizontal or vertical, but they should be parallel to each other.