The Competition is fast approaching, and Xiao D has decided to learn some more algorithms in this final stretch.
Xiao D has chosen
Xiao D plans to learn all
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
Xiao D has now numbered the basic algorithms as the first
Basic algorithms have no dependencies, while each extended algorithm
Out of all learning orders
The first line of input consists of two integers
The second line of input consists of
The third line of input consists of
The first line of output shall contain a single integer, the minimum possible value of
The second line of output shall contain
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.
Subtask # | Score | Constraints |
---|---|---|
1 | 5 | |
2 | 5 | |
3 | 10 | |
4 | 10 | |
5 | 30 | |
6 | 20 | |
7 | 20 | No additional constraints |
Sample Input 1 | Sample Output 1 |
6 2
|
7
|
Subtask | Score |
---|---|
1 | 5 |
2 | 5 |
3 | 10 |
4 | 10 |
5 | 30 |
6 | 20 |
7 | 20 |