울타리를 세우자

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

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

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

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

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

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

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

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

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

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