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,,n. He has also assigned a value wi 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,,n, where the ith element in the permutation pi represents that algorithm pi will be learnt ith.

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)=i=1n1|wpiwpi+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,,m, and the extended algorithms as the remaining nm algorithms m+1,m+2,,n.

Basic algorithms have no dependencies, while each extended algorithm i is dependent on one basic algorithm ui - and thus algorithm i must come after ui 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 ith integer will be wi, the value of the ith algorithm.
The third line of input consists of nm integers. The ith integer will be um+i, denoting that the algorithm m+i is dependent on the algorithm um+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 ith integer shall be pi, the ith 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

1mn106.
1wi1012.
1uim (m+1in)
Subtask # Score Constraints
1 5 m=n
2 5 n10
3 10 n20
4 10 wi10
5 30 n5000
6 20 n105
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


Submitting to 'learningtrack2'


You're not logged in! Click here to login


Submitting to 'learningtrack2'


You're not logged in! Click here to login


Submitting .cpp to 'learningtrack2'


You're not logged in! Click here to login

Time Limit: 3 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: LOJ #3068

Subtask Score
1 5
2 5
3 10
4 10
5 30
6 20
7 20