28409번 - 산 색칠 스페셜 저지

문제

히스토그램 모양의 도화지에 산 색칠을 반복하여 히스토그램 모양의 그림을 그리려고 한다.

히스토그램은 밑변이 $x$축에 평행한 한 개 이상의 직사각형이 공통된 밑변을 가지면서 빈틈없이 좌우로 붙어있는 도형을 말한다. 각 직사각형의 너비와 높이는 정수이며 서로 다를 수 있다.

한 번의 산 색칠은 다음과 같이 이루어진다.

• 도화지의 윗변 중 한 곳을 산의 정상으로 잡는다.
• 그에 맞는 산 모양 중 넓이가 최대인 모양으로 색칠한다.

산은 도화지를 벗어날 수 없으며, 이전의 색칠은 현재 색칠에 영향을 주지 않는다. 또한 직사각형의 왼쪽이나 오른쪽 끝은 산의 정상이 될 수 없다.

산의 구체적인 정의는 다음과 같다.

• 산의 정상이 가장 높은 히스토그램 모양이다.
• 산의 정상을 포함하는 왼쪽 부분은 높이가 단조 증가한다.
• 산의 정상을 포함하는 오른쪽 부분은 높이가 단조 감소한다.

단, 함수 $f$가 $x_1<x_2$인 모든 $x_1,x_2$에 대하여 $f(x_1)\le f(x_2)$을 만족하면 단조 증가한다고 하고, $f(x_1)\ge f(x_2)$을 만족하면 단조 감소한다고 한다.

산 색칠을 반복하여 주어진 그림을 그릴 수 있다면 최소한의 색칠 횟수로 그리고, 불가능하다면 -1을 출력하시오.

입력

첫 번째 줄에 도화지의 히스토그램을 이루는 직사각형의 개수 $N$이 주어진다. $(1\leq N\leq 200,円 000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 직사각형의 너비와 높이 $W_i,H_i$가 공백으로 구분되어 주어진다. $(1\leq W_i,H_i\leq 10^9)$

그 다음 줄에 그림의 히스토그램을 이루는 직사각형의 개수 $M$이 주어진다. $(1\leq M\leq 200,円 000)$

그 다음 줄부터 $M$개의 줄에 걸쳐 각 직사각형의 너비와 높이 $w_j,h_j$가 공백으로 구분되어 주어진다. $(1\leq w_j,h_j\leq 10^9)$

• 도화지와 그림의 총 너비는 같으며 10ドル^9$을 넘지 않는다. $(\sum{W_i} =\sum{w_j}\le 10^9)$
• 도화지는 그림을 포함한다.
• 인접한 직사각형은 높이가 서로 다르다. $(H_i\neq H_{i+1};$ $h_j\neq h_{j+1})$

출력

첫 번째 줄에 필요한 산 색칠의 최소 횟수를 출력한다. 만일 그림을 완성할 수 없다면 -1을 출력하고 종료한다.

두 번째 줄에 각 색칠에서 산의 정상이 도화지의 몇 번째 직사각형에 포함되는지 공백으로 구분하여 출력한다.

정답이 여러 가지라면 그중 아무거나 출력한다.

제한

노트