Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are n flights that must depart today, the i-th of them is planned to depart at the i-th minute of the day.

Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first k minutes of the day, so now the new departure schedule must be created.

All n scheduled flights must now depart at different minutes between (k + 1)-th and (k + n)-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.

Helen knows that each minute of delay of the i-th flight costs airport ci burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 300 000), here n is the number of flights, and k is the number of minutes in the beginning of the day that the flights did not depart.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 107), here ci is the cost of delaying the i-th flight for one minute.

Output

The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain n different integers t1, t2, ..., tn (k + 1 ≤ ti ≤ k + n), here ti is the minute when the i-th flight must depart. If there are several optimal schedules, print any of them.

Example

Input

5 2
4 2 1 10 2


Output

20
3 6 7 4 5 

Note

Let us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles. 

However, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 burles.
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
long long fac[1000006];
inline long long exp(long long x, long long n) {
  long long r = 1;
  x = x;
  while (n) {
    if (n % 2) r = (r * x) % 1000000007;
    x = (x * x) % 1000000007;
    n = n / 2;
  }
  return r;
}
inline long long mmi(long long a) {
  return exp(a, 1000000007 - 2) % 1000000007;
}
inline long long fact(long long n) {
  long long res = 1;
  for (long long i = 1; i < (n + 1); ++i) {
    res = (res * i) % 1000000007;
  }
  return res;
}
inline void fact_a() {
  fac[0] = 1;
  fac[1] = 1;
  for (long long i = 1; i < (105); ++i) {
    fac[i] = (fac[i - 1] * i) % 1000000007;
  }
}
inline long long inv_fact(long long n) {
  long long par = fac[n];
  long long res = mmi(par);
  return res;
}
inline long long comb(long long n, long long r) {
  if (n == r && r == 0) return 1;
  if (n < r) return 0;
  return ((fac[n] * inv_fact(r)) % 1000000007 * inv_fact(n - r)) % 1000000007;
}
struct triplet {
  long long a, b, c;
};
bool operator<(const triplet &t1, const triplet &t2) {
  if (t1.a < t2.a) return true;
  if (t1.a == t2.a && t1.b < t2.b) return true;
  if (t1.a == t2.a && t1.b == t2.b && t1.c < t2.c) return true;
  return false;
}
pair<long long, pair<long long, long long> > ex_gcd(long long a, long long b) {
  if (b == 0) {
    return make_pair(a, make_pair(1, 0));
  }
  pair<long long, pair<long long, long long> > p = ex_gcd(b, a % b);
  long long gcd = p.first;
  long long x1 = p.second.first;
  long long y1 = p.second.second;
  long long x = y1;
  long long y = x1 - (a / b) * y1;
  return make_pair(gcd, make_pair(x, y));
}
long long prime[3000006];
long long spf_prime[3000006];
void sieve() {
  prime[1] = 1;
  for (long long i = 2; i * i <= 3000000; i++)
    if (prime[i] == 0)
      for (long long j = i * i; j <= 3000000; j += i) prime[j] = 1;
}
void spf() {
  for (long long i = 2; i * i <= 3000000; i++)
    if (!spf_prime[i])
      for (long long j = i * i; j <= 3000000; j += i)
        if (!spf_prime[j]) spf_prime[j] = i;
  for (long long i = 2; i <= 3000000; i++)
    if (!spf_prime[i]) spf_prime[i] = i;
}
long long getparent_BIT(long long idx) { return idx - (idx & -idx); }
long long getnext_BIT(long long idx) { return idx + (idx & -idx); }
long long getsum_BIT(long long idx, long long BIT[], long long n) {
  long long sum = 0;
  while (idx > 0) {
    sum += BIT[idx];
    idx = getparent_BIT(idx);
  }
  return sum;
}
void update_BIT(long long idx, long long BIT[], long long val, long long n) {
  while (idx <= n) {
    BIT[idx] += val;
    idx = getnext_BIT(idx);
  }
}
void build_BIT(long long BIT[], long long a[], long long n) {
  for (long long i = 0; i < (n); ++i) {
    update_BIT(i, BIT, a[i], n);
  }
}
void comp_lps(string s, long long lps[], long long n) {
  long long i = 1, j = 0;
  while (i < n) {
    if (s[i] == s[j]) {
      lps[i++] = ++j;
    } else {
      if (j != 0)
        j = lps[j - 1];
      else
        lps[i++] = 0;
    }
  }
}
void dfs_l(long long u, vector<vector<long long> > &adj, long long status[]) {
  if (status[u] == 1) return;
  status[u] = 1;
  for (long long i = 0; i < (adj[u].size()); ++i) dfs_l(adj[u][i], adj, status);
}
long long dij(long long u, long long n,
              vector<vector<pair<long long, long long> > > &adj,
              long long status[]) {
  long long dist[n];
  for (long long i = 0; i < (n); ++i) dist[i] = 1000000000;
  dist[0] = 0;
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      q;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    pair<long long, long long> p;
    p = q.top();
    q.pop();
    long long x = p.second;
    long long w = p.first;
    if (status[x] == 1) continue;
    status[x] = 1;
    for (long long i = 0; i < (adj[x].size()); ++i) {
      long long ww = adj[x][i].first;
      long long y = adj[x][i].second;
      if (dist[x] + ww < dist[y]) {
        dist[y] = dist[x] + ww;
        q.push(make_pair(dist[y], y));
      }
    }
  }
  if (dist[n - 1] >= 1000000000) return -1;
  return dist[n - 1];
}
long long phi(long long n) {
  vector<long long> v;
  long long k = n;
  ;
  for (long long i = 2; i * i <= n; i++) {
    if (k % i == 0) {
      v.push_back(i);
      while (k % i == 0) k /= i;
    }
  }
  if (k > 1) v.push_back(k);
  long long ans = n;
  for (long long i = 0; i < (v.size()); ++i) ans -= (ans / v[i]);
  return ans;
}
struct trie {
  struct trie *left, *right;
  bool isend;
};
trie *get_trie() {
  trie *ptr = new trie;
  ptr->left = NULL;
  ptr->right = NULL;
  ptr->isend = false;
  return ptr;
}
bool isempty(trie *root) {
  if (root->left == NULL && root->right == NULL) return true;
  return false;
}
void insert_trie(trie *root, string key) {
  trie *ptr = root;
  for (long long i = 0; i < (key.size()); ++i) {
    if (key[i] == '0') {
      if (ptr->left == NULL) {
        ptr->left = get_trie();
      }
      ptr = ptr->left;
    } else {
      if (ptr->right == NULL) ptr->right = get_trie();
      ptr = ptr->right;
    }
  }
  ptr->isend = true;
}
trie *remove_trie(trie *root, string key, long long idx = 0) {
  if (root == NULL) return NULL;
  if (idx == key.size()) {
    if (isempty(root)) {
      delete (root);
      root = NULL;
    }
    return root;
  }
  if (key[idx] == '0')
    root->left = remove_trie(root->left, key, idx + 1);
  else
    root->right = remove_trie(root->right, key, idx + 1);
  if (isempty(root)) {
    delete (root);
    root = NULL;
  }
  return root;
}
long long search_trie(trie *root, string key) {
  trie *ptr = root;
  string s = "";
  for (long long i = 0; i < (key.size()); ++i) {
    if (key[i] == '0') {
      if (ptr->right != NULL) {
        ptr = ptr->right;
        s += '1';
      } else {
        ptr = ptr->left;
        s += '0';
      }
    } else {
      if (ptr->left != NULL) {
        ptr = ptr->left;
        s += '1';
      } else {
        ptr = ptr->right;
        s += '0';
      }
    }
  }
  long long res = 0;
  reverse(s.begin(), s.end());
  for (long long i = s.length() - 1; i >= (0); --i)
    res = res * 2 + (s[i] - '0');
  return res;
}
struct Comp {
  bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first) {
      return a.first < b.first;
    }
    return a.second > b.second;
  }
};
void dearr() {
  long long dar[1005];
  dar[0] = 1;
  dar[1] = 0;
  dar[2] = 1;
  for (long long i = 3; i < (1002); ++i) {
    dar[i] = (i - 1) * (dar[i - 1] + dar[i - 2]);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, k;
  cin >> n >> k;
  long long a[n];
  for (long long i = 0; i < (n); ++i) cin >> a[i];
  set<long long> s2;
  set<pair<long long, long long> > s1;
  for (long long i = 0; i < (3 * n); ++i) {
    s2.insert(k + 1 + i);
  }
  for (long long i = 0; i < (n); ++i) {
    s1.insert(make_pair(a[i], i + 1));
  }
  map<long long, long long> mp;
  while (!s1.empty()) {
    pair<long long, long long> g = *(s1.rbegin());
    s1.erase(g);
    long long val = g.first;
    long long pos = g.second;
    long long h = *(s2.lower_bound(pos));
    s2.erase(h);
    mp[pos] = h;
  }
  vector<long long> u;
  long long sum = 0;
  for (long long i = 0; i < (n); ++i) {
    u.push_back(mp[i + 1]);
    sum += ((mp[i + 1] - (i + 1)) * a[i]);
  }
  cout << sum << "\n";
  for (long long i = 0; i < (n); ++i) {
    cout << u[i] << " ";
  }
  cout << "\n";
}
