Cutting a Cake with a Hole

Time limit1sMemory limit128 MB

Summary

Given a square cake with a smaller square hole in its center, count how many pieces result from horizontal and vertical full-line cuts that only affect actual cake material.

Level: Medium6 of 10
Topics: Geometry, Union-find, BFS, Simulation
Solved: No attempts yet

Problem

Taesu received a special cake for his birthday. From above, the cake looks like a large square with a smaller square hole removed from its center.

The large square and the hole both have center (0, 0), and all of their sides are parallel to the x-axis or the y-axis. Half of the side length of the large square is LC, and half of the side length of the hole is LH.

The cake will be cut H times horizontally and V times vertically. The i-th horizontal cut is made along the entire line y = h_i, parallel to the x-axis. The i-th vertical cut is made along the entire line x = v_i, parallel to the y-axis. If a cutting line passes through the hole, only the parts that actually meet the cake are cut.

Find the number of cake pieces after all cuts are made.

Input

The first line contains LC and LH.

The second line contains H. The third line contains H integers h_i separated by spaces.

The fourth line contains V. The fifth line contains V integers v_i separated by spaces.

If H is 0, the third line is empty. If V is 0, the fifth line is empty.

Output

Print the number of cake pieces on the first line.

Constraints

2 <= LC <= 100
1 <= LH <= LC - 1
0 <= H, V <= 50
-LC + 1 <= h_i, v_i <= LC - 1

Examples4

Example 1
Input
```
5 3
2
1 -4
1
1
```
Expected output
```
6
```
Example 2
Input
```
10 5
0

2
-2 2
```
Expected output
```
4
```
Example 3
Input
```
10 5
1
1
2
-5 5
```
Expected output
```
6
```
Example 4
Input
```
50 5
2
40 -40
3
20 0 -20
```
Expected output
```
12
```