learningtrack2

Learning Track

The Competition is fast approaching, and Xiao D has decided to learn some more algorithms in this final stretch.

Xiao D has chosen \(n\) algorithms to learn, numbering them \(1, 2, \ldots, n\). He has also assigned a value \(w_i\) to each algorithm \(i\), according to a balance of its difficulty to learn vs practical value.

Xiao D plans to learn all \(n\) algorithms in some order. We can express such an order as a permutation \(p\) of \(1, 2, \ldots, n\), where the \(i^{th}\) element in the permutation \(p_i\) represents that algorithm \(p_i\) will be learnt \(i^{th}\).

Now, as he learns these algorithms, Xiao D also wants to keep the changes in value between consecutive algorithms low. For any one order of learning, he defines the cost of that order as the sum of differences in value between all consecutive pairs of algorithms learnt. Formally, a permutation \(p\) has weight \(w(p)\), where:
\[w(p) = \sum_{i = 1}^{n - 1}{|w_{p_i} - w_{p_{i + 1}}|}\] However, Xiao D soon discovered a complication: some algorithms have dependencies. For instance, learning Link-Cut Trees requires a knowledge of Splay Trees first. Xiao D divides his \(n\) algorithms into two categories: basic algorithms and extended algorithms.

Xiao D has now numbered the basic algorithms as the first \(m\) algorithms \(1, 2, \ldots, m\), and the extended algorithms as the remaining \(n - m\) algorithms \(m + 1, m + 2, \ldots, n\).

Basic algorithms have no dependencies, while each extended algorithm \(i\) is dependent on one basic algorithm \(u_i\) - and thus algorithm \(i\) must come after \(u_i\) in any learning order.

Out of all learning orders \(p\) which satisfy these dependencies, Xiao D wants to use one with minimum weight \(w(p)\). As he has not yet learnt any of the \(n\) algorithms, he cannot figure out how to find such an order - your task is to determine the minimum possible \(w(p)\), and find a permutation \(p\) achieving this minimum weight.

Input format

The first line of input consists of two integers \(n\) and \(m\), representing the total number of algorithms and the number of basic algorithms respectively.
The second line of input consists of \(n\) integers. The \(i^{th}\) integer will be \(w_i\), the value of the \(i^{th}\) algorithm.
The third line of input consists of \(n - m\) integers. The \(i^{th}\) integer will be \(u_{m + i}\), denoting that the algorithm \(m + i\) is dependent on the algorithm \(u_{m + i}\).

Output format

The first line of output shall contain a single integer, the minimum possible value of \(w(p)\).
The second line of output shall contain \(n\) integers, a permutation \(p\) valid under dependencies and with minimum weight. The \(i^{th}\) integer shall be \(p_i\), the \(i^{th}\) algorithm learnt in the order \(p\).
It can be proven that there always exists a valid order in which Xiaodou can learn all algorithms. If there are multiple orders with minimum weight, you may output any one of them.

Limits

\(1 \leq m \leq n \leq 10^6\).
\(1 \leq w_i \leq 10^{12}\).
\(1 \leq u_i \leq m\) \((m + 1 \leq i \leq n)\)

Subtask #	Score	Constraints
1	5	\(m = n\)
2	5	\(n \leq 10\)
3	10	\(n \leq 20\)
4	10	\(w_i \leq 10\)
5	30	\(n \leq 5000\)
6	20	\(n \leq 10^5\)
7	20	No additional constraints

Samples

Sample Input 1	Sample Output 1
6 2 1 3 2 4 5 6 2 2 1 1	7 2 3 1 4 5 6