BLACKOUT  Blackout
Caracas, as any other city, never sleeps, however, this is about to change as the Chief Officer Marcos “the little one” is scheduling some blackouts to search an important criminal and bring it to justice (If you like to know the criminal is known as “El Pran Malandroso”), the criminal is known for fainting when he doesn't see any source of light, so this is a perfect plan for Marcos “the little one” to trap him and capture him.
Marcos will give you the map where he is searching the criminal, the zone is given in a matrix and each value represents a block, surrounded by streets, where the number at the ith row and jth column denotes the number of people living in this block.
As Marcos “the little one” is a good officer, he doesn't wants to bother more than a specific number of people, as when he darken the zone, the people will going to be mad. That's what he called you for, Marcos will give you the northwest corner and the southeast corner, he will search in this specific area, causing a blackout.
Marcos will perform a series of blackouts in the city during the night, he will perform each blackout in a given zone, he will return the city all of its light and then he will perform another blackout, so on until he does Q blackouts, as the criminal is constantly moving in the city, the blackout will be independent and the area of searching will be always considered different.
Knowing this, can you maximize the area searched without exceeding the limit that Marcos gives you? (Citizens will be going mad when a blackout occurs)
INPUT:
The first line will contain 4 integers N, M, Q and K, denoting, respectively the N and M matrix size denoting an aerial view of the city, Q blackouts that Marcos the little one will do and K people that he wants to bother as much.
Then, N lines follow, each containing M integers, representing the people living in the block.
After that, Q lines will follow, each one containing four integers denoting the (i,j) point of the northwest corner and the (i,j) point of the southeast corner.
OUTPUT:
The first and only line of output should contain a number, representing the maximum area that Marcos can look for the criminal.
SAMPLE1:
INPUT 
OUTPUT 
3 3 2 20 1 2 3 4 5 6 7 8 9 1 1 3 3 1 1 2 2 
4 
Is important to note that each blackout is independent from the other, so, blackout affecting the zone (1,1) to (3,3) will lead to 45 people angry and 9 units of area, while a blackout from the zone (1,1) to (2,2) will get 12 people angry and 4 units of area. If the limit were 57, you could perform the two blackouts, giving a total result of 13.
SAMPLE2:
INPUT 
OUTPUT 
4 3 3 76 1 4 9 5 5 2 2 1 9 9 1 9 2 1 4 3 1 1 4 3 2 1 3 2 
16 
CONSTRAINTS:
1 <= N,M <= 2000
1 <= Q <= 1000
1 <= K <= 1000
0 <= (Ni,Mj) <= 1000
It is safe to say that there will be always an answer to this problem. (You will always find at least one blackout that doesn't bother more than K citizens)
hide comments
sharif ullah:
20170930 17:47:33
divide the problem into 2 parts 1>matrix sum && query in 0(1) 2>Knapsack 

kshubham02:
20170222 10:34:55
With cin and long long, TLE.


manjeet24feb:
20160322 15:45:23
Knapsack.... use scanf() instead of cin.. 

Sagnik Mondal:
20150819 21:58:01
can u please tell me where i m wrong ? ID 14931833


mkmostafa:
20150417 20:49:11
NOTE: DON'T USE "cin", USE "scanf" INSTEAD!! 

bony2023:
20140831 09:52:57
Now that's a great problem :D 

demon:
20131225 11:19:01
Please remove the SPOILERS! :/ 

Shakim:
20131211 14:14:35
take care of overflows!


BLANKRK:
20130630 12:46:33
nice mixing.... :D

Added by:  Venezuelan Programming League 
Date:  20120823 
Time limit:  0.200s0.600s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 