OGRADA

문제

Mirko and Slavko lived next door to each other in a small village and they were inseparable friends. 

One day they had a fight (Slavko went crazy because he found out Mirko was stealing rakija from his basement and eggs from the henhouse). 

When Mirko woke up the next morning, he was surprised to see that, during the night, Slavko had built a fence between their houses. Slavko's fence consists of N boards of varying heights placed in one row. 

Mirko, furious, decided to build an even bigger fence on his side, in front of Slavko's, so he doesn'thave to look at Slavko's fence. In front of each of Slavko's N boards he wants to put one of his own which will cover Slavko's board (in other words, he wants each of his boards to be at least as high as Slavko's board it is in front of). 

But Mirko doesn't have any boards at home (he forgot to steal them from Slavko) so he called his friend Lea who (conveniently) works in a sawmill. Lea brought N boards; each of the boards has a height and price. Unfortunately, when they started raising the fence, they noticed that Lea's boards may not be high enough to cover entire Slavko's fence. So they agreed they will build the fence anyway, but Mirko will pay only those boards which will cover Slavko's boards. 

Write a program which will help Lea arrange the boards and make the largest possible profit. 

입력

The first line contains an integer N (1 ≤ N ≤ 100 000), the number of boards in Slavko's fence. 

The second line contains N integers, the heights of the boards in Slavko's fence. The height of each board is between 1 and 10 000, inclusive. 

Each of the following N lines contains two integers, the height and price of one board which Lea brought. Both numbers will be between 1 and 10 000, inclusive. 

Lea's boards are numbered 1 to N, in the order in which they are given. 

출력

The first line of output should contain the largest profit Lea can achieve. 

The second line should contain the indices of Lea's boards in order in which they put them in front of Slavko's fence – the first number is the index of Lea's board which they will put in front of Slavko's first board, and so on. 

In the second line write the indexes of Lea's boards in order in which they put them in front of Slavko's fence. So the first number is the index of Lea's board they will put in front of Slavko's first board, and so on. 

Note: the optimal arrangement of the boards may not be unique. 

힌트

Clarification for first example: the heights of the boards which Mirko puts in front of Slavko's fence are in order 500, 300, 200, 600 i 400. Lea gets 800, 600, 0, 100 and 200 for them.

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

1700
4 2 1 5 3

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