#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-')  f = 0;
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
const int inf = 1e9;
const int maxn = 3000;
const int maxk = 10;
const int mod = 59393;
int n, k, a[maxk + 5], val[maxn + 5];
P lst[maxn + 5][maxn + 5];
int f[maxn + 5][maxn + 5];
int main() {
	//freopen("in.txt", "r", stdin);
	n = read(), k = read();
	rep(i, 0, k) a[i] = read();
	rep(i, 0, n - 1) {
		int x = 1;
		rep(j, 0, k) {
			val[i] = (val[i] + 1ll * x * a[j]) % mod;
			x = 1ll * x * i % mod;
		}
	}
	if(n == 1) {
		cout << val[0] << '\n';
		return 0;
	}
	ll cur = val[1] * n;
	rep(i, 1, n - 2) f[0][i] = -inf;
	rep(i, 1, n - 2) {
		rep(j, 0, n - 2) {
			if(i > j || f[i - 1][j] > f[i][j - i] + val[i + 1] - val[1]) {
				f[i][j] = f[i - 1][j];
				lst[i][j] = {i - 1, j};
			}
			else {
				f[i][j] = f[i][j - i] + val[i + 1] - val[1];
				lst[i][j] = {i, j - i};
			}
		}
	}
	cout << n - 1<< ' ' << cur + f[n - 2][n - 2] << '\n';
	vector<int> s;
	function<void(int, int)> dfs = [&] (int i, int j) {
		if(!i) return ;
		if(lst[i][j].se != j) s.pb(j - lst[i][j].se + 1);
		dfs(lst[i][j].fi, lst[i][j].se);
	};
	dfs(n - 2, n - 2);
	while(sz(s) < n) s.pb(1);
	sort(all(s));
	reverse(all(s));
	deque<P> q;
	rep(i, 0, sz(s) - 1) q.push_back({s[i], i + 1});// cout << s[i] << ' ' << i + 1 << '\n';
	vector<P> ans;
	rep(i, 1, n - 2) {
		assert(q.back().fi == 1);
		ans.pb({q.back().se, q.front().se});
		q.pop_back();
		q[0].fi --;
		if(q[0].fi == 1) {
			P x = q[0];
			q.pop_front();
			q.push_back(x);
		}
	}
	assert(sz(q) == 2);
	ans.pb({q[0].se, q[1].se});
	rep(i, 0, n - 2) cout << ans[i].fi << ' ' << ans[i].se << '\n';
	return 0;
}