#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9 + 7;
int main() {
//freopen("vrtic.inp", "r", stdin);
//freopen("vrtic.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t, n;
cin >> t >> n;
vector<int> p(n + 1);
for (int i = 1; i <= n; ++i) cin >> p[i];
vector<pair<int, int>> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i].first;
c[i].second = i + 1;
}
sort(c.begin(), c.end());
vector<bool> vis(n + 1, false);
vector<vector<int>> all_cycles;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
vector<int> cyc;
int ht = i;
while (!vis[ht]) {
vis[ht] = true;
cyc.push_back(ht);
ht = p[ht];
}
all_cycles.push_back(cyc);
}
}
map<int, vector<vector<int>>> cycles_by_len;
map<int, int> length_counts;
for (auto& cyc : all_cycles) {
cycles_by_len[cyc.size()].push_back(cyc);
length_counts[cyc.size()]++;
}
vector<int> cycles;
vector<int> limit;
for (auto& kv : length_counts) {
cycles.push_back(kv.first);
limit.push_back(kv.second);
}
int K = cycles.size();
vector<int> W(K);
int M = 1;
for (int i = 0; i < K; ++i) {
W[i] = M;
M *= (limit[i] + 1);
}
vector<vector<int>> cst_ma(n + 1, vector<int>(K, 0));
for (int S = 0; S < n; ++S) {
for (int i = 0; i < K; ++i) {
int L = cycles[i];
if (S + L <= n) {
if (L == 1) {
cst_ma[S][i] = 0;
} else if (L == 2) {
cst_ma[S][i] = c[S + 1].first - c[S].first;
} else {
int mx = 0;
for (int k = 0; k < L - 2; ++k) {
mx = max(mx, c[S + k + 2].first - c[S + k].first);
}
cst_ma[S][i] = mx;
}
}
}
}
vector<int> dp(M, inf);
vector<int> choice(M, -1);
dp[0] = 0;
vector<int> state(K, 0);
int S = 0;
for (int idx = 0; idx < M; ++idx) {
if (dp[idx] != inf) {
for (int i = 0; i < K; ++i) {
if (state[i] < limit[i]) {
int nxt_idx = idx + W[i];
int new_cost = max(dp[idx], cst_ma[S][i]);
if (new_cost < dp[nxt_idx]) {
dp[nxt_idx] = new_cost;
choice[nxt_idx] = i;
}
}
}
}
if (idx == M - 1) break;
for (int i = 0; i < K; ++i) {
state[i]++;
S += cycles[i];
if (state[i] <= limit[i]) break;
state[i] = 0;
S -= cycles[i] * (limit[i] + 1);
}
}
cout << dp[M - 1] << "\n";
int ht = M - 1;
vector<int> cycle_types_used;
while (ht > 0) {
int i = choice[ht];
cycle_types_used.push_back(i);
ht -= W[i];
}
reverse(cycle_types_used.begin(), cycle_types_used.end());
vector<int> kq(n + 1);
int current_S = 0;
for (int i : cycle_types_used) {
int L = cycles[i];
vector<int> cyc = cycles_by_len[L].back();
cycles_by_len[L].pop_back();
vector<pair<int, int>> arr(L);
int l = 0, r = L - 1;
for (int k = 0; k < L; ++k) {
if (k % 2 == 0) arr[l++] = c[current_S + k];
else arr[r--] = c[current_S + k];
}
for (int k = 0; k < L; ++k) {
kq[cyc[k]] = arr[k].second;
}
current_S += L;
}
for (int i = 1; i <= n; ++i) {
cout << kq[i] << (i == n ? "" : " ");
}
cout << "\n";
}
