/**
 * Programare dinamică. Definim c(i, j) costul minim pentru a salva primele
 * i mesaje, având în final o selecție de tip j. Dacă D(i) = x, atunci
 *   c(i, x) = min {
 c(i - 1, x) + T1,      (salvăm manual mesajul j)
 c(i - 1, x) + T2,      (adăugăm mesajul j la selecția existentă)
 c(i - 1, y) + T3 + T2  (închidem o altă selecție și deschidem una pentru x)
 }
 *   c(i, y) = c(i - 1, y) + T1  (păstrăm selecția și salvăm manual mesajul j)
 **/
#include <stdio.h>

#define MAX_N 10000
#define MAX_K 1000
#define INFINITY 50000 * 10000
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

int cost[MAX_N + 1][MAX_K + 1];
int d[MAX_N + 1];   // Directorul fiecărui mesaj
int min[MAX_N + 1]; // Poziția primelor două minime de pe fiecare linie
int sel[MAX_N + 1]; // Vectorul-soluție: sel[i] = selecția activă la pasul i

int main() {
  int n, k, t1, t2, t3, t12, costx;

  FILE *f = fopen("alpine.in", "r");
  fscanf(f, "%d %d %d %d %d", &n, &k, &t1, &t2, &t3);
  t12 = MIN(t1, t2);

  // Citim directoarele și calculăm matricea de costuri. În paralel, calculăm
  // indicele minimului pe fiecare linie.
  for (int i = 1; i <= n; i++) {
    fscanf(f, "%d", &d[i]);
    costx = cost[i - 1][d[i]] + t12;
    for (int j = 1; j <= k; j++) {
      costx = MIN(costx, cost[i - 1][j] + t3 + t2);
    }
    cost[i][d[i]] = costx;
    min[i] = d[i];
    for (int j = 1; j <= k; j++) {
      if (j != d[i]) {
        cost[i][j] = cost[i - 1][j] + t1;
        if (cost[i][j] < cost[i][min[i]]) {
          min[i] = j;
        }
      }
    }
  }
  fclose(f);

  f = fopen("alpine.out", "w");
  if (t1 * n <= cost[n][min[n]] + t3) {
    // Este mai eficient să nu avem niciodată o selecție
    fprintf(f, "%d\n", t1 * n);
    for (int i = 1; i <= n; i++) {
      fputc('1', f);
    }
    fprintf(f, "\n");
  } else {
    // Calculăm traseul spre linia 0
    sel[n] = min[n];
    for (int i = n; i >= 1; i--) {
      if ((d[i] != sel[i]) ||
          (cost[i][sel[i]] == t2 + cost[i - 1][sel[i]])) {
        sel[i - 1] = sel[i];
      } else {
        sel[i - 1] = min[i - 1];
      }
    }

    // Tipărim soluția
    fprintf(f, "%d\n", cost[n][min[n]] + t3);
    for (int i = 1; i <= n; i++) {
      if (sel[i] != sel[i - 1]) {
        fputs("32", f);
      } else if (d[i] == sel[i]) {
        fputc('2', f);
      } else {
        fputc('1', f);
      }
    }
    fputs("3\n", f);
  }
  fclose(f);
}