KPMATRIX - Matrix


The company you work in has got a secret job to do. Just a few persons know what it is all about. To keep a secret every programmer works on a small part of the project.

Your job is as follows. You are given a matrix of integer numbers with N rows and M columns. Also two integer numbers A and B are given. Your task is to find a number of submatrices of a given matrix with the sum of elements between A and B inclusively.

Input

The first line contains two integer numbers N and M (1 ≤ N, M ≤ 250). After that matrix description follows. N lines with M numbers each. The last line contains two integer numbers A and B (-10^9 ≤ A ≤ B ≤ 10^9). All numbers separated with spaces. It's guaranteed that for every submatrix the absolute value of sum of it's elements will not exceed 10^9.

Output

Write to the output the number of submatrices of a given matrix with sum of their elements between A and B inclusively.

Example

Input:
3 3
1 0 0
0 1 0
0 0 1
1 3

Output:
26

hide comments
wutiruo: 2022-10-03 17:11:18

is there any other better algorithm other than o(n^2 mlogm)

Sigma Kappa: 2020-06-05 22:36:52

OK I am getting TLE with an O(n^2mlog(m)) algo, where n <= m. What did you use?
EDIT: Nevermind, got Acc.

Last edit: 2020-06-06 00:29:03
Palashvijay4O: 2016-08-10 06:41:23

code running till 20th test case even if it is not working for smaller test cases. Please have a look into it.

abdou_93: 2016-03-18 20:04:37

O(n^3 log n)

Noureldin Yosri: 2016-03-16 19:43:07

don't take this problem seriously :3

nour samir: 2014-07-20 21:41:49

this problem is solvable by using segment tree and DP

Hussain Kara Fallah: 2014-01-03 09:25:19

I love this kind of problems
just try the 1D version :D

rajnish: 2012-05-17 10:51:16

is there any other better algorithm other than o(n^2*m^2)

Prabakaran: 2011-02-21 20:48:00

hw is the output 26 for the above test case?


Added by:Pavel Kuznetsov
Date:2007-02-23
Time limit:1s-1.841s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:IT Festival Arkhangelsk 2006