Build the Fence

Time limit1sMemory limit128 MB

Summary
Assign Taewoo's priced boards to Doyun's fence positions, using a height covering rule, to maximize total paid price and output the matching.
Level

Medium7 of 10

Topics
Greedy, Sorting, Binary search
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

  1. Example 1

    Input
    5
400 200 500 600 400
200 400
300 600
400 200
500 800
600 100
    Expected output
    1700
4 2 1 5 3

  2. Example 2

    Input
    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
    Expected output
    95
8 6 1 7 5 4 2 3