Celestial Being

Celestial Being(CB) is a private military organization which is aimed to rid the wars and con icts in the world, using the advanced mobile suit gundam. But due to high cost of manufacture a gundam, only four gundams were produced, named Exia, Dynames, Kyrios and Virtue. Gundams use a kind of mysterious particles known as GN particle to communicate with each other, and GN particle always transport messages parallel to coordinate axises. Thus when in battle, four gundams always form a rectangle whose sides are parallel to x-axis or y-axis, and the coordinates of all gundams are integers. Have known celestial being is going to attack their military base, colonel of the enemy, Sergei Smirnov ordered to release some detectors to detect the positions of gundams when they arrive. The military base is a rectangle feld of with with corners (0, 0), (w, 0), (0, h) and (w, h). Each detector has a parameter d
and is either horizontal detector or vertical detector. A horizontal detector with parameter d can detect all positions on the lines y = h, where h is a multiple of d, while a vertical detector with parameter d can detect all positions on the lines x = v, where v is a multiple of d. If a position can be detected by k(k > 0) or more detectors, a gundam on that position will be discovered by the enemy. Got the parameters of all detectors from spy, the tactical forecaster of celestial being, Sumeragi Lee wants too know how many conservative battle positions are there. Can you help her? A
conservative battle position is a combination of four distinct points with integer coordinates, each stands for a position of one gundam such that no gundam can be detected by k or more detectors, and the four points form a rectangle whose sides parallel to x-axis or y-axis. Note that change the positions of two gundams will result in a new battle positon.

Each test case begins with five integers w(1 <= w <= 10⁸), h(1 <= h <= 10⁸), m(0 <= m <= 20), n(0 <= n <= 20)
and k(k >= 1) on the first line, m is the number of horizontal detectors and n is the number of vertical
detectors. Then m + n lines follows, the first m line are the parameters of horizontal detectors, and the
rest n lines are the parameters of vertical detectors. All parameters are positive integers.

Output one line for each test case, the number of conservative battle positions.

1 1 0 0 1
1 1 1 0 2
2
1 1 1 1 2
2
2
5 3 1 1 1
2
2
5 3 1 1 2
2
2
5 3 1 1 3
2
2

24
24
0
72
720
2160

Cauchy (Special thanks WJH)

2010 Asia Regional Chengdu Site —— Online Contest