울타리를 세우자

시간 제한1초메모리 제한128 MB

요약
도윤의 울타리 각 위치에 태우의 판자를 배정해 높이 조건을 만족시키며 받는 총 금액을 최대화하고 배치를 출력해야 합니다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

도윤이는 높이가 서로 다를 수 있는 판자 N개를 일렬로 세워 울타리를 만들었다. 시형이는 그 울타리가 보이지 않도록, 자기 마당 쪽에서 도윤이의 각 판자 앞에 판자를 하나씩 세우려고 한다.

태우가 가져온 판자도 N개이며, 각 판자에는 높이와 가격이 정해져 있다. 태우의 판자 하나를 도윤이의 판자 하나 앞에 세웠을 때, 태우의 판자 높이가 도윤이의 판자 높이 이상이면 시형이는 그 판자의 가격을 태우에게 지불한다. 더 낮으면 그 판자에 대해서는 돈을 지불하지 않는다.

태우가 받을 수 있는 총액이 최대가 되도록 태우의 판자를 배치하라.

입력

첫째 줄에 도윤이의 판자 개수를 나타내는 정수 N이 주어진다. 1 <= N <= 100000이다.

둘째 줄에는 도윤이의 각 판자 높이를 나타내는 정수 N개가 주어진다. 모든 높이는 1 이상 10000 이하이다.

다음 N개 줄에는 태우가 가져온 판자의 정보가 입력 순서대로 주어진다. 각 줄에는 판자의 높이와 가격이 공백으로 구분되어 주어진다. 높이와 가격은 모두 1 이상 10000 이하이다.

태우의 판자는 입력되는 순서대로 1번부터 N번까지 번호가 매겨진다.

출력

첫째 줄에 태우가 받을 수 있는 최대 금액을 출력한다.

둘째 줄에 도윤이의 1번 판자부터 N번 판자까지, 각 판자 앞에 세울 태우의 판자 번호를 순서대로 출력한다.

최적의 배치가 여러 개라면 그중 아무거나 출력해도 된다.

예제2

  1. 예제 1

    입력
    5
400 200 500 600 400
200 400
300 600
400 200
500 800
600 100
    예상 출력
    1700
4 2 1 5 3

  2. 예제 2

    입력
    8
70 40 80 70 50 60 20 30
30 10
30 20
30 25
60 15
60 5
50 30
40 5
40 5
    예상 출력
    95
8 6 1 7 5 4 2 3