The land is ablaze! Help firefighters extinguish the fire and prevent it from spreading!
The land has a form of a rectangle divided into unit squares. Unit squares represent fields, which are in danger of catching fire (some of them may be already on fire). A squad of courageous firefighters wants to extinguish the fire. To do so, they use aeroplanes which can transport water and drop it onto blazing fields. Each firefighter uses one aeroplane. Aeroplanes are different - some fly really slowly whereas other dash very fast, some can transport little water whereas other are very capacious. Faster aeroplanes are able to drop water more often. More voluminous planes can drop more water in a single flight. Each aeroplane is described by two parameters - t and w. Value t denotes minimal time that has to pass between consequtive flights of the aeroplane. Value w denotes amount of water that can be dropped by the aeroplane in each flight. Water can be dropped from this aeroplane for the first time in minute t,
Firefighters can drop water from planes from different altitudes, therefore the areas on which dropped water will fall may differ (each time a firefighter can drop water, he decides from what altitude he will do so). The area is always a rectangle with sides parallel to the land's rectangle. The higher the water is dropped from, the more fileds it will land on, but less water will land on each of these fields. If a firefighter drops an amount U of water on area with width w and height h, then the amount of water that will fall on each field of the area is given by formula: ⌊Uw×h⌋
Each field of the land may be ablaze. Fields are described by two parameters - fireDamage and maximalDamage. Parameter fireDamage denotes the magnitude of fire on the field (the higher the value, the greater the fire on the field). The longer the field is ablaze, the more damage is done to it. Therefore, every minute on each field the value of maximalDamage will be decreased by: max If on a field value of fireDamage will exceed value of maximalDamage, the field will be considered as burnt totally. From that moment on it will no longer be on fire, the fireDamage value of this field will be set to 0 and will not be changed any more.
Fire can spread. Depending on weather conditions (specified as parameter A), fire may spread faster or slower. Each field has 4 neighboring fields (called naighbors, neighbors have common side with the field). Each minute fire spreads as following:
1. Let F be a field, fd be fireDamage value on that field and S be equal to the sum of fireDamage values of neighbors of F.
2. If S >= 5*A-1, then fd is increased by value 1 + fdA. Otherwise it is increased by fdA.
Each minute, firstly maximalDamage values are decreased (using current fireDamage values) and secondly fireDamage values are increased. Changes of fireDamage are done simultaneously for all fields. If additionaly during that minute water was dropped on a field, after changes in damage the fireDamage value of this field will be decreased by the amount of water dropped onto it (if fireDamage would be negative after such operation, it will be set to 0 instead).
Due to infallible weather forecast, after minute T (at the end of minute T, after all possible changes in that minute) will come thunderstorm. In that moment fire on all fields will be extinguished (fireDamage value set to 0).
In the first line there will be two integers W and H (1<=W,H<=75) denoting the width and height of the land.
Each of the following H lines will contain W float numbers - number in j-th row and i-th column will denote initial fireDamage of field (i,j).
After that come another H lines, each containing W float numbers - number in j-th row and i-th column denotes initial maximalDamage of field (i,j). In given input maximalDamage for a field will always be larger than fireDamage for that field.
Next line contains an integer N (1<=N<=20) - the number of firefighters. Each of next N lines will contain 2 integers: t and w representing parameters t and w of aeroplane which the firefighter uses. Aeroplane described in i-th line has id equal i (it may be used in output).
Next line will contain parameter A (float number).
Last line will contain integer T (0<T<=1000) - time after which will come thunderstorms.
First line of output must contain integer D equal to the number of times that water was dropped from aeroplane. Each of next D lines must contain six integers: id, t, x, y, w and h. These numbers denote respectively: id number of aeroplane, minute in which it drops water, x and y coordinates, width and height of rectangular area on which water is dropped (water will be dropped on the rectangle with corners in points (x,y), (x+w,y), (x,y+h) and (x+w,y+h) ).
If the output is correct, for each field will be calculated difference between value maximalDamage at the beginning (values given in input) and at the end (after thunderstorm). Your program will receive score equal to X+Y, where X is the sum of those differences over all fields and Y is sum of maximalDamage values (after thunderstorm) over all totally burnt fields (hence value added to the score by every totally burnt field will equal its initial maximalDamage). You should minimize this value.
For each test case with 0 <= W * H < 500, your program will receive SIGTERM signal after 180 seconds of execution. After another 15 seconds, it will be killed with Time Limit Exceeded status.
For each test case with 500 <= W * H, your program will receive SIGTERM signal after 600 seconds of execution. After another 15 seconds, it will be killed with Time Limit Exceeded status.
For each test the available memory is limited to 1 GB and the size of the output that can be generated by the program is limited to 20 MB.
4 4
12.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00
0.00 0.00 0.00 12.00
40.00 40.00 40.00 40.00
40.00 40.00 40.00 40.00
40.00 40.00 40.00 40.00
40.00 40.00 40.00 40.00
2
3 10
5 11
0.3
20
/*
Easy test?
*/
8
1 3 1 1 1 1
1 6 3 3 2 2
1 9 3 4 1 1
1 12 4 3 1 1
1 15 4 3 1 1
2 5 1 1 1 1
2 10 1 1 1 1
2 15 4 3 1 1
Example output would receive score 82,570883. Pictures below present result and state of fields after every minute. Tables denote values of fireDamage and maximalDamage respectively.