The Promised Land

All submissions for this problem are available.
Years after the Ishval Civil War, the Ishvalan refugees have now found a safe place for themselves which is a rectangular piece of land, surrounded by fences. The land can be thought of as a 2d grid which extends $N$ units vertically and $M$ units horizontally. It is divided into $N$ horizontal rows, which are numbered from $1$ to $N$, as you move from top to bottom and into $M$ vertical columns numbered from $1$ to $M$, from left to right. There are $X$ rivers flowing in a horizontal direction, each flowing in a different row and covering the entire row. Similarly, there are $Y$ rivers flowing in a vertical direction, each flowing in a different column and covering the entire column. The people want to build houses of dimensions $S \times S$ on the remaining land. What is the maximum number of houses of the given dimensions that could be built on the remaining land, such that no part of any house is in a river and no two houses overlap? ### Input:  The first line contains $T$, the number of test cases. Then the test cases follow.  For each test case, the first line contains $N$ and $M$.  Then the second line contains $X$ , $Y$ and $S$ denoting the number of rivers flowing horizontally, number of rivers flowing vertically and the dimension of the house.  The next line contains $X$ integers $x_{i}$ denoting the indices of rows in which river flows horizontally.  The next line contains $Y$ integers $y_{i}$ denoting the indices of columns in which the river flows vertically. **Note**:  $x_{i}$ and $y_{i}$ are given in increasing order.  When $X$ or $Y$ are zero, the line containing $x_{i}$ and $y_{i}$ is skipped respectively in the input (instead of a blank line). ### Output: For each test case, print a single line containing the maximum number of houses that can be built. ### Constraints  $1\leq T\leq 100$  $1 \leq N,M \leq 10^{4}$  $0 \leq X \leq N$  $0 \leq Y \leq M$  $1 \leq S \leq min(N,M)$  $1 \leq x_{i} \leq N$  $1 \leq y_{j} \leq M$  $x_i > x_{i1}$ for all $2 \leq i \leq X$  $y_i > y_{i1}$ for all $2 \leq i \leq Y$ ### Sample Input: ``` 2 7 8 1 2 2 5 4 8 6 5 2 0 1 1 4 ``` ### Sample Output: ``` 6 20 ``` ### Explanation: The given figure corresponds to the first test case. ``` 7 8 1 2 2 5 4 8 ``` ![](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i... =480x420) As shown in the figure, the maximum number of houses of dimension $2\times2$ that could be built on the remaining land is $6$.Author:  sachin_yadav 
Editorial  https://discuss.codechef.com/problems/ISHVALA 
Tags  basicmath, dcod2019, sachin_yadav, simple 
Date Added:  19102019 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 