Page Contents

### Adding Squares SOLUTIONS OCTOBER CHALLENGER 2020

There are N different vertical lines on the plane, i-th of which is defined by the equation x=ai (0≤ai≤W) and M different horizontal lines, i-th of which is defined by the equation y=bi (0≤bi≤H). You must add one line of the form y=k (0≤k≤H, k≠bi for every 1≤i≤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 a1,a2,…,aN
Third line will contain M different integers b1,b2,…,bM
Output:
Output the maximal possible number of squares with different area on the plane after adding a new line.

Constraints
1≤W,H,N,M≤105
N≤W+1
M≤H
0≤ai≤W for every 1≤i≤N
0≤bi≤H for every 1≤i≤M
50 points : 1≤H,W≤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.

LOGIC WILL BE UPLOADED SOON STAY TUNE AND