// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 3005, M = 55, P = 59393;

int n, K, w[N], a[M], pre[N], d[N], t, c;

LL f[N];

int fa[N], p[N];

void inline pToF() {
    for (int i = 1; i <= n - 2; i++) d[p[i]]++;
    p[n - 1] = n;
    for (int i = 1, j = 1; i < n; i++, j++) {
    	while (d[j]) j++;
    	fa[j] = p[i];
    	while (i < n - 1 && --d[p[i]] == 0 && p[i] < j) fa[p[i]] = p[i + 1], ++i;
    }
}

int main() {
	read(n), read(K);
	
	for (int i = 0; i <= K; i++) read(a[i]);
	for (int i = 0; i < n; i++) {
		int x = i, s = 0, v = 1;
		for (int j = 0; j <= K; j++) {
			s = (s + 1ll * v * a[j]) % P;
			v = 1ll * v * x % P;
		}
		w[i] = s;
	}
	if (n == 1) {
		printf("%d %d\n", 0, w[0]);
		return 0;
	}
	memset(f, 0xcf, sizeof f);
	f[0] = 1ll * n * w[1];
	for (int i = 1; i <= n - 2; i++) {
		for (int j = 1; j <= i; j++) {
			if (chkMax(f[i], f[i - j] + w[j + 1] - w[1]))
				pre[i] = i - j;
		}
	}
	printf("%d %lld\n", n - 1, f[n - 2]);
	int x = n - 2;
	while (x) {
		++c;
		int z = x - pre[x];
		while (z--) p[++t] = c;
		x = pre[x];
	}
	pToF();
	for (int i = 1; i < n; i++)
		printf("%d %d\n", i, fa[i]);
    return 0;
}