Description

A factory has received orders for $n$ products. Each product must be processed in workshop A first and then in workshop B. At any moment, each workshop can process at most one product.

For product $i$, its processing times in workshops A and B are $A_i$ and $B_i$, respectively. Determine an order to process the $n$ products that minimizes the total processing time.

The total processing time is defined as the time from starting the first product until all products have finished processing in both workshops A and B.

Input Format

• The first line contains a single integer $n$, the number of products.
• The second line contains $n$ integers, the processing times of the $n$ products in workshop A.
• The third line contains $n$ integers, the processing times of the $n$ products in workshop B.

Output Format

• The first line contains one integer, the minimal total processing time.
• The second line contains one processing order that achieves the minimal total processing time. Output the product indices (from $1$ to $n$) separated by spaces.

5
3 5 8 7 10
6 2 1 4 9

34
1 5 4 2 3

Hint

Constraints: $1 \leq n \leq 1000$, $1 \leq A_i, B_i \leq 1000$.

Translated by ChatGPT 5