F. Дожди и зонтики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп живет на координатной прямой в точке $$$x = 0$$$. Он отправился в гости к своему другу, который живет в точке $$$x = a$$$. Поликарп двигается только слева направо, преодолевает одну единицу длины за одну секунду.

В настоящий момент идет дождь, поэтому некоторые участки его пути находятся под дождем. Формально: дождь льет на $$$n$$$ непересекающихся отрезках, $$$i$$$-й отрезок под дождем имеет вид $$$[l_i, r_i]$$$ ($$$0 \le l_i < r_i \le a$$$).

На координатной прямой есть $$$m$$$ зонтиков, $$$i$$$-й зонтик расположен в точке $$$x_i$$$ ($$$0 \le x_i \le a$$$) и имеет массу $$$p_i$$$. В начале своего путешествия Поликарп не несет ни одного зонтика.

По пути из $$$x = 0$$$ в $$$x = a$$$ Поликарп может подбирать и оставлять зонтики. Как подбор, так и сброс зонтика осуществляется мгновенно. Поликарп может нести произвольное количество зонтиков одновременно. Так как Поликарп не хочет промокнуть, то при перемещении из $$$x$$$ в $$$x + 1$$$ он должен обязательно нести хотя бы один зонтик, если отрезок $$$[x, x + 1]$$$ находится под дождем (то есть существует такое $$$i$$$, что $$$l_i \le x$$$ и $$$x + 1 \le r_i$$$).

Написанное выше условие — единственное требование к маршруту Поликарпа. Например, допустимо дойти без зонтика до точки, в которой начинается дождь, подобрать в этой точке зонтик и продолжить путь уже под зонтиком. Например, Поликарп может сменить зонтик, находясь под дождем — подобрать новый зонтик и одновременно оставить старый, находясь в промежуточной точке участка под дождем.

При каждом перемещении на единицу вправо к усталости Поликарпа прибавляется суммарная масса всех зонтиков, которые он несет.

Сможет ли Поликарп добраться из точки $$$x = 0$$$ в точку $$$x = a$$$? В случае положительного ответа найдите наименьшую суммарную усталость, с которой Поликарп придет в точку $$$x = a$$$, если будет подбирать и оставлять зонтики оптимальным образом.

Входные данные

В первой строке входных данных записано три целых числа $$$a$$$, $$$n$$$ и $$$m$$$ ($$$1 \le a, m \le 2000, 1 \le n \le \lceil\frac{a}{2}\rceil$$$) — точка, в которой живет друг Поликарпа, количество отрезков, в которых идет дождь и количество зонтиков.

В следующих $$$n$$$ строках записано по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i < r_i \le a$$$) — границы $$$i$$$-го отрезка, на котором льет дождь. Гарантируется, что никакая пара отрезков не пересекается. Иными словами, для любой пары отрезков $$$i$$$ и $$$j$$$ либо $$$r_i < l_j$$$, либо $$$r_j < l_i$$$.

В следующих $$$m$$$ строках записано по два целых числа $$$x_i$$$ и $$$p_i$$$ ($$$0 \le x_i \le a$$$, $$$1 \le p_i \le 10^5$$$) — расположение и масса $$$i$$$-го зонтика соответственно.

Выходные данные

Выведите «-1» (без кавычек), если Поликарп не сможет добраться из точки $$$x = 0$$$ в точку $$$x = a$$$. Иначе выведите одно целое число — наименьшую суммарную усталость, с которой Поликарп придет в точку $$$x = a$$$, если будет подбирать и оставлять зонтики оптимальным образом.

Примеры
Входные данные
10 2 4
3 7
8 10
0 10
3 4
8 1
1 2
Выходные данные
14
Входные данные
10 1 1
0 9
0 5
Выходные данные
45
Входные данные
10 1 1
0 9
1 5
Выходные данные
-1
Примечание

В первом тестовом примере единственная возможная стратегия — взять четвертый зонтик в точке $$$x = 1$$$ и идти с ним до точки $$$x = 7$$$ (суммарная усталость в точке $$$x = 7$$$ будет равна $$$12$$$), оставить его, пройти от $$$x = 7$$$ до $$$x = 8$$$ без зонтика, взять третий зонтик в точке $$$x = 8$$$ и идти с ним до конца (суммарная усталость в точке $$$x = 10$$$ будет равна $$$14$$$).

Во втором тестовом примере единственная возможная стратегия — взять первый зонтик, пройти с ним до точки $$$x = 9$$$, выбросить его и завершить путь без зонтика.