Parts Process

Time Limit: 2 Seconds
Memory Limit: 65536 KB

To build a machine, a lot of parts need to be produced. A question is how to
arrange the processing order to minimize the total delay time of the parts.

**Input**

The input consists of no more than 20 test cases.

The first line of each test case contains an integer n (<= 15). Then n lines
follow.

The i-th (start from 1) line contains two positive integers pi and di, where
pi is the i-th part's process time (that is, pi minute(s) must be taken to produce
the i-th part), and di the deadline of the i-th part.

These lines are in ascending order of di. The total process time is no more
than 100.

**Output**

Define:

Fi - the finishing time of the i-th part;

Di - the delay time of the i-th part, that is, Di = max{(Fi - di) , 0};

T - the total delay time, that is, T = sum(Di).

For each test case, two lines should be outputted.

The first line contains the minimal T.

The second line contains n integers, indicating the processing order of the
parts.

If there are more than one orders, you should output the lexicographically smaller
one.

**Sample Input**

3

3 3

2 3

1 20

**Sample Output**

2

1 2 3

Author:

**CHEN, Zhimin**
Source:

**ZOJ Monthly, October 2003**
Submit
Status