시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 60 | 4 | 4 | 7.143% |
동규는 큰 벽을 2일동안 만들려고 한다.
가게에는 N종류의 블록이 있다. 이 블록의 개수는 매우 많기 때문에, 품절되는 경우는 없다. 각 블록의 가격은 Ci이며, 1*1*Di 크기이다.
2일 중 하루는 모든 블록을 수평으로 쌓을 것이고, 다른 날에는 수직으로 쌓을 것이다.
벽은 L미터 크기의 평평한 땅 위에 만들 것이다. 벽은 실루엣으로 묘사한다.
실루엣은 (x1, y1), (x2, y2), ..., (Xm, Ym)와 같이 좌표의 연속으로 표현하고, 벽의 위쪽 경계선이다.
실루엣에 대해서 좀 더 자세히 설명하면 다음과 같다.
예를 들어, 길이가 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
10 2 3 1 4 10 6 0 0 4 0 4 6 6 6 6 0 10 0 6 0 10 4 10 4 6 6 6 6 10 10 10
204