Bojarka

Сегодня 29 октября. Задача посвящается тем, кто в юности читал "Как закалялась сталь" и помнит номер своего комсомольского билета. Но решать её можно всем.

Город в осаде. Дров нет. Железнодорожная ветка проложена к лесу, дальше раздваивается и идёт вдоль края леса, направо и налево, но совсем недалеко. Лес вдоль рельсов вырублен и вывезен. А дальше есть насыпь, но нет рельсов. Вдоль насыпи заготовленные штабеля брёвен.

Немного рельсов удалось добыть, демонтировав никому сейчас не нужную железнодорожную веку к дачам - R рельсов по M метров каждый. Но в какую сторону тянуть ветку - налево, направо, или сразу в обе стороны? Комсомольцы Леонтий и Порфирий были отправлены на разведку (Леонтий - налево, Порфирий - направо) с заданием осмотреть все штабеля и записать, на каком расстоянии они от конца рельсов и какого объёма. Через несколько часов (или дней) усталые и замёрзшие разведчики вернулись, каждый принёс блокнот с записями.

Разработайте программу, которая на основании значений R и M, а также записей Леонтия и Порфирия определяет сколько кубометров дров удастся привезти в город, если распорядиться рельсами наилучшим образом.

Входные данные. В первой строке - разделённые пробелом натуральные числа R, M, L и P: количество рельсов, длина одного рельса в метрах и количество штабелей, описанных Леонтием и Порфирием. В следующих L строках записи Леонтия - пары натуральных чисел, разделённых пробелом, первое число - растояние до штабеля дров в метрах, второе число - объём штабеля в кубометрах. Так же организованы данные Порфирия в следующих P строках. Записи каждого разведчика упорядочены по возрастанию расстояния. Все числа в этой задаче, кроме длины рельса, не превышают 100000, ну а рельсы, если верить гуглу, точно не более 500 м.

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

Пример. При вводе вот таких данных
20 25 7 5
250 40
400 10
600 80
610 90
1200 50
2000 70
2050 50
30 20
40 50
195 10
170 60
300 20
программа должна вывести 180: потратив 10 рельсов, вывезем 40 кубометров слева, ещё 8 рельсов позволят вывезти 140 кубометров справа, и это оптимальный вариант.