시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 0 0 0.000%

문제

도윤이는 작은 마을에 살았다. 옆집에는 시형이가 살았고, 둘은 떼어놓을 수 없는 절친이다.

어느 날, 그들이 싸웠다. 시형이가 도윤이의 지하실에서 라키아 술과  닭장에서 달걀을 훔치는 것을 도윤이가 봤기 때문이다.

다음 날 아침에 일어났을 때, 시형이는 매우 놀랐다.

어제 밤에 도윤이가 둘의 집 사이에 울타리를 친것을 봤기 때문이다.

도윤이의 울타리는 하나의 행에 다양한 높이의 N보드로 이루어져 있다.

N보드란 높이 N의 나무판을 말한다.

분노한 시형이는 도윤이의 울타리의 꼴도 보기 싫어서, 도윤이의 울타리 앞, 자기 쪽 마당에 더 큰 울타리를 짓기로 결심했다.

시형이는 도윤이의 N보드를 가릴 자신의 보드를 도윤이의 N보드 앞에 놓을 것이다.

즉, 도윤이의 보드 이상의 높이를 가진 보드를 그 앞에 세우겠다는 것이다.

하지만 시형이는 거지라서 집에 보드가 하나도 없다. 보드를 훔치는 것을 깜빡한 모양이다.

그래서 그는 제재소에서 일하는 그의 친구 태우를 불렀다.

태우는 N보드를 가져왔는데, 각각의 보드는 높이와 가격이 달랐다.

여전히 시형이는 운이 없는 것 같다.

불행하게도, 시형이와 태우가 울타리를 세우기 시작할 때, 그들은 도윤이의 울타리 전체를 덮을만큼의 울타리를 가지고 있지 않은 것을 알아차렸다.

어쨌든 그들은 울타리를 그냥 짓기로 했지만, 시형이는 도윤이의 보드를 덮는 것을 성공한 보드에 대해서만 태우에게 돈을 지불하기로 했다.

즉, 높이가 4인 도윤이 보드에 높이가 3인 보드를 세우도록 했다면 태우는 높이가 3인 보드를 시형이에게 공짜로 줘야 한다.

또, 높이가 3인 도윤이 보드에 높이가 5인 보드를 세우도록 했다면 태우는 높이가 5인 보드에 대한 돈을 시형이에게 받을 수 있다.

태우가 싫지 않다면, 태우가 최대한 많은 돈을 받을 수 있도록 도와주자.

입력

첫 줄에 도윤이의 보드 개수를 나타내는 정수 N이 주어진다. 1≤N≤100000 이다.

둘째 줄에는 각각의 도윤이의 보드 높이를 나타내는 N개의 수들이 주어진다. 높이는 1이상 10000이하이다.

뒤따르는 N개 줄에는 각각 2개의 수가 들어있다.

첫 번째 수는 태우가 가져온 보드의 높이이고, 두 번째 수는 태우가 가져온 보드의 가격이다.

높이와 가격은 1이상 10000이하이다.

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

출력

출력의 첫 줄은 태우가 시형이에게 받을 수 있는 최대 금액을 출력한다.

둘째 줄에는 도윤이의 울타리 앞에 놓을 순서를 출력한다.

순서를 출력하는 방식은 다음과 같다.

입력에서 매겨진 번호를 이용해서 순서대로 매겨진 번호를 출력한다.

예를 들어 순서가 3번, 1번, 2번 순이라면   3 1 2   를 출력한다.

참고 : 보드의 배치순서는 유일하지 않을 수 있다.

예제 입력

5
400 200 500 600 400
200 400
300 600
400 200
500 800
600 100

예제 출력

1700
4 2 1 5 3

힌트