cho.sh

산 색칠

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

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

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

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

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

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

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

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

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

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

입력

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

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

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

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

  • 도화지와 그림의 총 너비는 같으며 10910^9을 넘지 않는다. (∑W_i=∑w_j≤109)(\sum{W\_i} =\sum{w\_j}\le 10^9)
  • 도화지는 그림을 포함한다.
  • 인접한 직사각형은 높이가 서로 다르다. (H_i≠H_i+1;(H\_i\neq H\_{i+1}; h_j≠h_j+1)h\_j\neq h\_{j+1})

출력

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

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

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

힌트

(a) 예제 1의 도화지와 그림(b) 예제 2의 도화지와 그림