/*
TASK: SLIDESV
LANG: C
*/
#include <stdio.h>
#include <stdlib.h>

#define BYLA_DAT "SLIDES.DAT"
#define BYLA_REZ "SLIDES.REZ"

#define N_MAX            1010
#define M_MAX            2010

    /* slidės tipo aprašas */
    typedef struct slide {
        int nr, l;  /* numeris ir ilgis */
    } slide;
    
    int   N, M;
    slide S[M_MAX];
    int   kaina[N_MAX][M_MAX],
          paimta[N_MAX][M_MAX];

/* elementų palyginimo funkcija, reikalinga
   standartinei rikiavimo funkcijai qsort() */
int cmpf(const void *a, const void *b)
{
    return ((slide *)a)->l - ((slide *)b)->l;
}

void skaityk(void)
{
    int   i;
    FILE *f = fopen(BYLA_DAT, "r");
    fscanf(f, "%d %d\n", &N, &M);
    for (i = 1; i <= M; i++) {
        fscanf(f, "%d\n", &S[i].l);
        S[i].nr = i;
    }
    fclose(f);
}

void rasyk(void)
{
    int   n, m;
    FILE *f = fopen(BYLA_REZ, "w");
    fprintf(f, "%d\n", kaina[N][M]);
    for (n = N, m = M; n != 0;) {
        if (paimta[n][m]) {
            fprintf(f, "%d %d\n", S[m-1].nr, S[m].nr);
            m -= 2;
            n -= 1;
        } else 
            m -= 1;
    }
    fclose(f);
}

int main(void)
{
    int n, m;
    int kaina1, kaina2;
    
    skaityk();
    /* Išrikiuojame slides pagal jų ilgius */
    qsort(&S[1], M, sizeof(slide), cmpf);
    
    /* Uždavinį sprendžiantis algoritmas (dinaminis programavimas) */
    for (n = 1; n <= N; n++) {
        kaina[n][2*n]  = kaina[n-1][2*n-2] + (S[2*n].l - S[2*n-1].l);
        paimta[n][2*n] = 1;
        for (m = 2*n+1; m <= (M - 2*(N-n)); m++) {
            kaina1 = kaina[n][m-1];
            kaina2 = kaina[n-1][m-2] + (S[m].l - S[m-1].l);
            if (kaina1 < kaina2) {
                kaina[n][m]  = kaina1;
                paimta[n][m] = 0;
            } else {
                kaina[n][m]  = kaina2;
                paimta[n][m] = 1;
            }
        }
    }
    
    rasyk();
    return 0;
}