CIGLE

문제

Ljubo is planning to build a big wall in just two days. 

A store offers N distinct types od bricks in unlimited supply. Each brick type has specific price C_i and dimensions 1×1×D_i. 

One day Ljubo will place bricks in the wall horizontally, while the other day he will place bricks vertically. He can choose if he will place bricks horizontally the first day or the second day and he will, of course, choose the cheaper variant. 

The wall lies on the flat ground and is L meters long, and can be described by silhouette, a sequence of points (x₁, y₁), (x₂, y₂), ..., (x_M, y_M) that follows the upper border of the wall. Silhouette begins with upper left corner of the wall and ends with upper right corner of the wall. Specifically: 

• M is an even number 
• x₁ = 0, x_M = L 
• x_2k-1 < x_2k , x_2k = x_2k+1, for each k 
• y_2k-1 = y_2k, for each k 

For example, a wall of length 7 in the left illustration is described by silhouette (0, 2), (3, 2), (3, 1), (5, 1), (5, 3), (7, 3), while the wall on the right illustration is described by silhouette (0, 4), (2, 4), (2, 6), (7, 6). 

[이미지 1]

Given the data for available brick types as well as the wall silhouette after the first day and the final wall silhouette, write a program that will calculate the cost of the cheapest possible total price to build a wall in two days as described. 

입력

The first line contains one integer L (2 ≤ L ≤ 10⁹), wall length. 

The second line contains one integer N (1 ≤ N ≤ 100), the number of brick types. 

The next N lines contain two natural numbers each D and C (2 ≤ D ≤ 1000, 1 ≤ C ≤ 1 000 000), the brick length and price for each brick type. 

The next line contains one even integer M1 (2 ≤ M₁ ≤ 100 000), the number of points on a wall silhouette after the first day. 

The next M₁ lines contains points coordinates, two non-negative integers each. 

The next line contains one even integer M₂ (2 ≤ M₂ ≤ 100 000), the number of points on a wall silhouette after the second day. 

The next M₂ lines contains points coordinates, two non-negative integers each. 

Wall height will not exceed 10⁹. 

For each x coordinate, the height of first wall silhouette will be less than or equal to the height of the second wall silhouette. 

출력

Output one integer, the minimum cost to build the wall. 

Note: The input data will be such that it will be possible to build the wall in the way described, and the minimum cost will not exceed 10¹⁸.