-->

## Adding Squares  Codechef October Long challenge Problem Code-

### problem Statement-

There are $N$ different vertical lines on the plane, $i$-th of which is defined by the equation $x={a}_{i}$ ($0\le {a}_{i}\le W$) and $M$ different horizontal lines, $i$-th of which is defined by the equation $y={b}_{i}$ ($0\le {b}_{i}\le H$). You must add one line of the form $y=k$ ($0\le k\le H$$k\ne {b}_{i}$ for every $1\le i\le M$) to the plane. What is the maximum possible number of squares with different areas you can obtain on the plane? (Squares can have other lines passing through them)

### Input:

• First line will contain $4$ integers $W$$H$$N$$M$
• Second line will contain $N$ different integers ${a}_{1},{a}_{2},...,{a}_{N}$
• Third line will contain $M$ different integers ${b}_{1},{b}_{2},...,{b}_{M}$

### Output:

Output the maximal possible number of squares with different area on the plane after adding a new line.

### Constraints

• $1\le W,H,N,M\le {10}^{5}$
• $N\le W+1$
• $M\le H$
• $0\le {a}_{i}\le W$ for every $1\le i\le N$
• $0\le {b}_{i}\le H$ for every $1\le i\le M$

• 50 points : $1\le H,W\le 1000$
• 50 points : Original constraints

### Sample Input:

10 10 3 3
3 6 8
1 6 10


### Sample Output:

3


### Explanation:

You can get $3$ different squares if you add a line $y=4$. The three squares are:

• Square with top-left corner at (6, 6) and bottom-right corner at (8, 4) with an area of 4.
• Square with top-left corner at (3, 4) and bottom-right corner at (6, 1) with an area of 9.
• Square with top-left corner at (3, 6) and bottom-right corner at (8, 1) with an area of 25.

Learn Bitset-

### C++ bitset and its application - GeeksforGeeks

www.geeksforgeeks.org › c-bitset-and-its-application

### bitset - C++ Reference - Cplusplus.com

www.cplusplus.com › Reference › <bitset>