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