Плоштадите се места во градовите каде се одржуваат најразлични активности. Во главниот град на една земја има плоштад со правоаголен облик со димензии N и M (единици). Во последната предвидена реконструкција, плоштадот треба да се поплочи со травертински плочи со ширина 1 и различни должини.

Во таа земја често се случуваат протести (се разбира на плоштадот) арно ама секогаш има и контра протести од други граѓани. Градоначалникот добил идеја да го подели плоштадот на 2 дела (со искршена линија од отсечки последователно паралелни со една од границите на плоштадот), за секоја од двете групи да си има свој дел (горен и долен). За да е видлива поделбата, одлучено е при поплочувањето, во едниот дел сите плочи да се поставуваат во хоризонтала, а во другиот дел во сите во вертикала.

Изведувачот има на располагање K различни типови на плочи. Една плоча чини Pi пари и има должина Di (ширината на сите плочи е 1). Може да се смета дека од секој тип на плочи има по неограничен број на парчиња.

Изведувачот мора да го поплочи комплетно целиот простор (да не остави никакви дупки). Исто така тој не смее да ги крши плочите (треба да ги избере така што ќе може да ги смести комплетно).

Изведувачот сака да го направи тоа за најмалку можно изгубени пари за набавка на плочите. Тој има можност да избере во кој од двата дела ќе ги реди плочите хоризонтално, а во кој вертикално.

Утврдете колку најмалку пари може да потроши изведувачот за набавка на потребните плочи.

Влез

Во првиот ред се наоѓаат димензиите на плоштадот: броевите N (2 <= N <= 1 000 000 000) и M (2 <= M <= 1 000 000 000), одделени со едно празно место.
Во вториот ред е даден број K - бројот на различни типови на плочи (1 <= K <= 100).
Во секој од следните К редови се наоѓаат по два броја Di и Pi (2 <= Di <= 1 000, 1 <= Pi <= 1 000 000), одделени со по едно празно место.
Во следниот ред се наоѓа бројот S (2 <= S <= 100 000, S е парен број) .
Во секој од следните S редови се наоѓа по еден пар броеви, Xi и Yi, одделени со по едно празно место, кои ги претставуваат координатите на едно од темињата на границата помеѓу горниот и долниот дел од плоштадот, соодветно. (1<=i<=S) Координатите се секогаш дадени во редослед од лево кон десно, долж границата. Дополнително секогаш важи дека X1=0 и XS=N т.е. првото теме лежи на левата страна, а последното на десната страна на плоштадот.

На пример, за плоштадот даден на сликата, бројот на темиња на контурата на границата е S = 8, а паровите координати на темињата долж границата по редослед од лево кон десно, се: (0, 3), (1, 3), (1, 4), (3, 4), (3, 2), (7, 2), (7, 0), (9, 0). (Види Пример 3)

Забелешка:
За тест случаи кои носат 25% од поените ќе важи: S = 2 и M,N <= 100 000.
За тест случаи кои носат 25% од поените ќе важи: S = 2 и 100 000 < M,N.
За тест случаи кои носат 25% од поените ќе важи: S <> 2 и M,N <= 100 000.
За тест случаи кои носат 25% од поените ќе важи: S <> 2 и 100 000 < M,N.

Излез

Во првиот и единствен ред е запишана најмалата сума на пари која мора да ја потроши изведувачот за набавка на плочите.

Забелешка: Тест примерите се избрани така што секогаш ќе постои решение.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
4 6
2
2 2
4 3
2
0 2
4 2

излез
18

влез
4 6
2
2 2
4 5
2
0 2
4 2

излез
24

влез
9 6
3
2 2
3 4
4 2
8
0 3
1 3
1 4
3 4
3 2 
7 2
7 0
9 0

излез
42

Објаснување за првиот тест пример: На сликата се дадени неколку примери на поплочување на плоштадот. Во првиот и третиот пример даден на сликата горниот дел на плоштадот е поплочен вертикално, а долниот хоризонтално. Изведувачот ќе потроши најмалку пари ако поплочи како што е дадено на третата слика. Минималната сума пари во овој случај е: 4*3+2*3=18 (12 за горниот дел, а 6 за долниот).