시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 3 3 6.383%

문제

동규는 큰 벽을 2일동안 만드려고 한다.

가게에는 N종류의 블럭이 있다. 이 블럭의 개수는 매우 많기 때문에, 품절되는 경우는 없다. 각 블럭의 가격은 Ci이며, 1*1*Di 크기이다.

2일 중 하루는 모든 블럭을 수평으로 쌓을 것이고, 다른 날에는 수직으로 쌓을 것이다.

벽은 L미터 크기의 평평한 땅 위에 만들 것이다. 벽은 실루엣으로 묘사한다.

실루엣은 (x1, y1), (x2, y2), ..., (Xm, Ym)와 같이 좌표의 연속으로 표현하고, 벽의 위쪽 경계선이다.

실루엣에 대해서 좀 더 자세히 설명하면 다음과 같다.

M은 짝수이다.

x1 = 0, xm = L

x2k-1 < x2k, x2k = x2k+1

y2k-1 = y2k

예를 들어, 길이가 7인 벽이 있을 때, 왼쪽 그림을 실루엣으로 표현하면, (0,2), (3,2), (3,1), (5,1), (5,3), (7,3)이며, 오른쪽 그림은 (0,4), (2,4), (2,6), (7,6)이다.

현재 가게에서 파는 블럭의 정보와 첫째 날 완성한 벽의 실루엣과 둘째 날 완성한 벽의 실루엣이 주어졌을 때, 벽을 완성하는데 필요한 금액의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 벽의 길이 L이 주어진다. (2 ≤ L ≤ 109)

둘째 줄에는 블럭 종류의 수 N이 주어진다. (1 ≤ N ≤ 100)

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

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

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

다음 줄에는 둘째 날 실루엣 점의 개수 M2가 주어진다. (2 ≤ M2 ≤ 100,000, M2은 짝수)

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

벽의 높이는 109를 넘지 않는다.

각각의 x좌표에 대해서, 첫째 날 벽의 실루엣의 높이는 둘째날 벽의 실루엣의 높이보다 작거나 같다.

출력

첫째 줄에 벽의 완성하는데 드는 최소 비용을 출력한다. 항상 벽을 만들 수 있는 경우만 입력으로 주어지며, 벽을 완성하는데 드는 최소 비용은 1018을 넘지 않는다.

예제 입력

7
2
2 5
3 7
6
0 2
3 2
3 1
5 1
5 3
7 3
4
0 4
2 4
2 6
7 6

예제 출력

92

힌트