3068 「2019 集训队互测 Day 1」学习轨迹

马上就要比赛了，小 D 决定突击学习一些算法。

他要学习的算法共有 $n$ 个，这些算法被依次标号为 $1,2,\cdots,n$。

小 D 根据学习难度以及实用价值等方面，给每个算法定了一个价值。其中，编号为 $i$ 的算法的价值是 $w_i$。

小 D 想要以某种顺序学完所有的这 $n$ 个算法。我们把他学习的顺序可以看做一个 $1,2,\cdots,n$ 的排列 $p$，其中第 $i$ 项 $p_i$ 表示第 $i$ 个学习的算法的编号。

小 D 不希望连续学习的算法之间价值差异过大。对于一种学习方案，他定义这种方案的代价为相邻两个学习的算法的价值差之和。形式化地，对于排列 $p$，我们定义他的权值 $w(p)$ 为：

$$w(p)=\sum_{i=1}^{n-1}\left \lvert w_{p_i}-w_{p_{i+1}} \right \rvert$$

但是，小 D 很快发现了一些问题：有的算法之间具有依赖关系，例如学习 LCT 需要先学习 Splay。小 D 把这些算法分成了两类：基础算法和延伸算法。

基础算法共有 $m$ 个，为了方便，小 D 把它们编号为 $1,2,\cdots,m$；延伸算法是剩下的 $n-m$ 个算法，编号为 $m+1,m+2,\cdots,n$。

对于每个延伸算法 $i(m+1\le i\le n)$，该算法会依赖恰好一个基础算法，记作 $u_i(1\le u_i\le m)$。即，算法 $i$ 必须要在算法 $u_i$ 之后学习。

小 D 想要知道，在所有满足这些依赖关系的学习序列 $p$ 中，$w(p)$ 最小的那一个。

因为小 D 还没开始学这 $n$ 个算法，所以他并不会算。请你帮他求出 $w(p)$ 的最小值，以及一个取到该最小值的排列 $p$。

从标准输入读入数据。

第一行包括两个空格隔开的整数 $n,m$，分别表示算法的总数，基础算法的个数。

第二行包括 $n$ 个空格隔开的整数，其中第 $i$ 个数 $w_i$ 表示算法 $i$ 的价值。

第三行包括 $n-m$ 个空格隔开的整数，其中第 $i$ 个数 $u_{m+i}$ 表示延伸算法 $m+i$ 依赖的算法的编号。

输出到标准输出。

第一行包括一个整数，表示 $w(p)$ 的最小值。

第二行包括 $n$ 个空格隔开的整数，其中第 $i$ 个数 $p_i$ 表示最优解中，第 $i$ 个学习的算法编号。

可以证明，在题目的限制下，小 D 一定可以学完所有的算法，即合法的 $p$ 一定存在。如果有多个使 $w(p)$ 取最小值的合法的 $p$，你可以输出其中任意一个。

评分方式

对于每组测试数据，若你输出的 $w(p)$ 是正确的，则你可以得到该测试点 $60\%$ 的分数。

此外，若你输出的排列 $p$ 是一组可以使 $w(p)$ 取最小值的合法方案，则你可以得到该测试点剩余 $40\%$ 的分数。

请注意，即使对于某些测试点，你可能只想要得到部分分，但是你仍然需要严格按照输出格式进行输出。

子任务

对于所有测试数据，$1\le n\le 10^{6}$，$1\le m\le n$，$1\le w_i\le 10^{12}$，$1\le u_i\le m(m+1\le i\le n)$。

本题共 $7$ 个子任务，对于每个子任务，你的得分为你在该子任务中所有测试数据上得分的最低者。

各子任务的特殊限制见下表：