Build the Fence

Doyun built a fence from N boards placed in a row. The boards may have different heights. Sihyeong wants to hide Doyun's fence by placing one of his own boards in front of each of Doyun's boards.

Taewoo brings exactly N boards. Each board has a height and a price. If Taewoo's board is placed in front of a Doyun board and its height is at least the height of that Doyun board, Sihyeong pays Taewoo that board's price. If it is shorter, Taewoo receives nothing for that board.

Arrange Taewoo's boards so that the total amount Taewoo receives is as large as possible.

The first line contains an integer N, the number of Doyun's boards. 1 <= N <= 100000.

The second line contains N integers, the heights of Doyun's boards. Every height is between 1 and 10000, inclusive.

The next N lines describe Taewoo's boards in input order. Each line contains two integers: the board's height and its price. Both values are between 1 and 10000, inclusive.

Taewoo's boards are numbered from 1 to N in the order they are given.

On the first line, print the maximum amount of money Taewoo can receive.

On the second line, print the numbers of Taewoo's boards placed in front of Doyun's boards 1 through N, in order.

If several optimal arrangements exist, you may print any one of them.