Building a Wall

Donggyu wants to finish a wall of length L over two days.

A store sells N types of blocks in unlimited quantity. The i-th block costs C_i and has size 1 x 1 x D_i.

On one of the two days, every block is placed horizontally; on the other day, every block is placed vertically. Which day uses which orientation is not fixed.

The wall is built on flat ground of length L. At each point in time, the wall shape is described by a silhouette. A silhouette is the upper boundary of the wall, written as a sequence of coordinates (x_1, y_1), (x_2, y_2), ..., (x_M, y_M).

A silhouette satisfies the following conditions.

• M is even.
• x_1 = 0 and x_M = L.
• For every k, x_{2k-1} < x_{2k} and x_{2k} = x_{2k+1}.
• For every k, y_{2k-1} = y_{2k}.

For example, for a wall of length 7, the silhouette of the left figure is (0, 2), (3, 2), (3, 1), (5, 1), (5, 3), (7, 3), and the silhouette of the right figure is (0, 4), (2, 4), (2, 6), (7, 6).

Given the block information, the silhouette after the first day, and the silhouette after the second day, find the minimum total cost needed to complete the wall after the second day.

The first line contains the wall length L. (2 <= L <= 10^9)

The second line contains the number of block types N. (1 <= N <= 100)

Each of the next N lines contains a block length D and cost C. (2 <= D <= 1,000, 1 <= C <= 1,000,000)

The next line contains the number of points M_1 in the first-day silhouette. (2 <= M_1 <= 100,000, and M_1 is even)

Each of the next M_1 lines contains one coordinate of the first-day silhouette, in order. All coordinates are nonnegative integers.

The next line contains the number of points M_2 in the second-day silhouette. (2 <= M_2 <= 100,000, and M_2 is even)

Each of the next M_2 lines contains one coordinate of the second-day silhouette, in order. All coordinates are nonnegative integers.

The wall height does not exceed 10^9. For every x-coordinate, the first-day wall height is less than or equal to the second-day wall height.

Print the minimum cost required to complete the wall. The input is always such that the wall can be built, and the minimum cost does not exceed 10^18.