비

길이가 긴 직육면체 상자의 길이 방향에 수직으로 높이가 서로 다른 방수 벽이 놓여 있다. 이웃한 두 벽 사이의 거리는 1센티미터이다. 상자에는 뚜껑이 없으며, 위에서 비가 충분히 내리면 물이 최대한 많이 고인다. 일부 벽은 미리 정해진 값 이하의 정수만큼 높이를 늘릴 수 있다. 상자에 고일 수 있는 물의 양이 최대가 되도록 높이를 늘려야 하는 벽의 최소 개수를 구하시오. 답을 구하는 프로그램 rain을 작성하시오.

참고: 상자의 너비를 1센티미터로 가정하므로 물의 양은 세제곱센티미터로 계산한다. 상자의 앞벽과 뒷벽(우리를 향한 벽과 뒤쪽 벽)은 각 벽의 높이와 벽 높이의 가능한 증가분보다 높다고 본다. 상자의 왼쪽 벽과 오른쪽 벽은 각각 왼쪽 벽과 오른쪽 벽에 해당하는 방수 벽과 일치하며, 높이를 늘린 뒤에도 마찬가지이다.

표준 입력의 첫째 줄에는 벽의 개수 N이 주어진다. 둘째 줄에는 상자 안에서 왼쪽에서 오른쪽으로 놓인 순서대로 각 벽의 높이가 센티미터 단위로 주어진다. 다음 줄에는 높이를 늘릴 수 있는 벽의 개수 K가 주어진다. 이어서 높이를 늘릴 수 있는 벽의 수만큼 줄이 주어진다. 각 줄에는 벽 번호와 늘릴 수 있는 최대 높이(센티미터)가 주어진다. 벽 번호는 0부터 시작한다.

프로그램은 표준 출력에 정확히 하나의 공백으로 구분된 두 정수를 출력해야 한다. 각각 높이를 늘린 벽의 최소 개수와 높이를 늘린 뒤 상자에 고일 수 있는 물의 최대량이다.

• 1 < N < 1 000 000
• 0 < K ≤ N; 각 벽의 처음 높이는 1 000 000보다 작은 양의 정수이다.
• 벽 높이의 최대 증가분은 1 000 000보다 작은 양의 정수이다.

위치 2의 벽은 높이를 늘려도 물의 양이 변하지 않으므로 늘리지 않는다. 위치 4의 벽 높이를 1센티미터 늘린다. 그러면 물의 총량이 1세제곱센티미터 늘어난다.