벽 쌓기

동규는 이틀 동안 길이 L인 벽을 완성하려고 한다.

가게에는 N종류의 블록이 충분히 많이 있다. i번째 블록의 가격은 C_i이고 크기는 1 x 1 x D_i이다.

이틀 중 하루에는 모든 블록을 수평으로 놓고, 다른 하루에는 모든 블록을 수직으로 놓는다. 어느 날이 어느 방향인지는 정해져 있지 않다.

벽은 길이 L인 평평한 땅 위에 세우며, 각 시점의 벽 모양은 실루엣으로 나타낸다. 실루엣은 벽의 위쪽 경계선을 나타내는 좌표열 (x_1, y_1), (x_2, y_2), ..., (x_M, y_M)이다.

실루엣은 다음 조건을 만족한다.

• M은 짝수이다.
• x_1 = 0, x_M = L이다.
• 모든 k에 대해 x_{2k-1} < x_{2k}이고 x_{2k} = x_{2k+1}이다.
• 모든 k에 대해 y_{2k-1} = y_{2k}이다.

예를 들어 길이가 7인 벽에서, 왼쪽 그림의 실루엣은 (0, 2), (3, 2), (3, 1), (5, 1), (5, 3), (7, 3)이고, 오른쪽 그림의 실루엣은 (0, 4), (2, 4), (2, 6), (7, 6)이다.

가게에서 파는 블록 정보, 첫째 날이 끝났을 때의 실루엣, 둘째 날이 끝났을 때의 실루엣이 주어진다. 둘째 날의 벽을 완성하기 위해 필요한 총비용의 최솟값을 구하라.

첫째 줄에 벽의 길이 L이 주어진다. (2 <= L <= 10^9)

둘째 줄에 블록 종류의 수 N이 주어진다. (1 <= N <= 100)

다음 N개의 줄에는 블록의 길이 D와 가격 C가 주어진다. (2 <= D <= 1,000, 1 <= C <= 1,000,000)

다음 줄에 첫째 날 실루엣을 이루는 점의 개수 M_1이 주어진다. (2 <= M_1 <= 100,000, M_1은 짝수)

다음 M_1개의 줄에는 첫째 날 실루엣의 좌표가 순서대로 주어진다. 모든 좌표는 음이 아닌 정수이다.

다음 줄에 둘째 날 실루엣을 이루는 점의 개수 M_2가 주어진다. (2 <= M_2 <= 100,000, M_2는 짝수)

다음 M_2개의 줄에는 둘째 날 실루엣의 좌표가 순서대로 주어진다. 모든 좌표는 음이 아닌 정수이다.

벽의 높이는 10^9를 넘지 않는다. 모든 x좌표에서 첫째 날 벽의 높이는 둘째 날 벽의 높이보다 작거나 같다.

벽을 완성하는 데 드는 최소 비용을 출력한다. 항상 벽을 만들 수 있는 입력만 주어지며, 최소 비용은 10^18을 넘지 않는다.