Задача C. Туча над городом ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Недавно Леонард Хофстедтер вернулся из экспедиции на северный полюс. Целью этой экспедиции было создание особых туч, из которых идет розовый снег. По мнению Леонарда это — лучший подарок любой девушке.

К сожалению, городские власти не спешат обрадоваться новой достопримечательности. Ведь мало того, что из туч идет розовый снег, причем очень много — каждую секунду на квадратный метр выпадает S сантиметров снега, по какой-то причине все тучи получаются правильной прямоугольной формы и портят вид.

У Леонарда есть только один шанс склонить власти на свою сторону — провести испытания тучи, наблюдая за уменьшенной версией и новейшим макетом города в течение T секунд. Макет города имеет форму огромного прямоугольника, на котором отмечены все улицы города. Все улицы считаются бесконечными полосками, параллельными либо левому, либо нижнему краю макета. Испытания будут проводиться следующим образом: тучку разместят над макетом так, что ее стороны будут параллельны его сторонам, а левый нижний угол совпадет с левым нижним углом макета. Затем смоделируют ветер: в течение секунды туча не будет двигаться, затем моментально переместится на заданный вектор, и так все T секунд. До начала испытания макет хранится в строжайшей тайне и может выглядеть практически как угодно. Например, так:

Сегодня вечером Леонарду пришло письмо от анонимного любителя розового снега, в котором подробно описывался макет, туча и ветер, которые будут смоделированы на предстоящих испытаниях. Вас же Леонард просит посчитать, сколько при этом выпадет снега на улицы макета.

Решения, работающие при M = 0, U = 0, V = 0, будут оцениваться из 20 баллов.

Решения, работающие при M = 0, будут оцениваться из 40 баллов.

Решения, работающие при x_i + w_i, y_i + h_i ≤ 1000, T ≤ 100, будут оцениваться из 60 баллов.

Рисунок в условии соответствует первому примеру.

Формат входного файла

В первой строке находятся четыре целых числа: N — количество улиц в городе, параллельных левому краю макета, M — количество улиц в городе, параллельных нижнему краю макета, T — время наблюдения за тучей, S — количество снега, выпадающее на один квадратный метр за секунду (0 ≤ N, M ≤ 10⁴, 0 < N + M, 1≤ T ≤ 10⁶, 1 ≤ S ≤ 100).

В следующей строке находятся четыре целых числа: H, W — длины сторон тучи, параллельные левому и нижнему краю макета (1 ≤ H, W ≤ 10⁵); U, V — на сколько увеличивается расстояние от тучи до левого и нижнего краев макета, соответственно, при ее сдвиге (0 ≤ U, V ≤ 10⁵).

В следующих N строках содержится по два целых числа x_i, w_i — расстояние от левого края макета до левой стороны улицы и ее ширина (0 ≤ x_i ≤ 10⁵, 1 ≤ w_i ≤ 10⁵).

В следующих M строках содержится по два целых числа y_i, w_i — расстояние от нижнего края макета до нижней стороны улицы и ее ширина (0 ≤ y_i ≤ 10⁵, 1 ≤ w_i ≤ 10⁵). Никакие две параллельные улицы не пересекаются и не имеют общих сторон.

Формат выходного файла

В выходной файл выведите единственное число — сколько снега выпадет на улицы макета за время наблюдения.

Примеры тестов

1 1 10 1
3 2 1 1
5 1
5 2

14

2 0 10 1
2 2 1 0
1 1
3 2

12