// by iodwad
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>

#define int long long

using namespace std;

const int MAXN = 3000;
const int MOD = 59393;

int n, K;
int C[MAXN + 5], a[MAXN + 5];
int f[MAXN + 5][MAXN + 5], h[MAXN + 5][MAXN + 5];
int prufer[MAXN + 5];

bool chkmax(int &x, int y) { return x < y ? x = y, true : false; }

int cnt;
void dfs(int x, int y, int z) {
  if (!x) return;
  prufer[++cnt] = z;
  if (h[x][y] == y - 1) dfs(x - 1, y - 1, z);
  else dfs(x - 1, h[x][y], z + 1);
}


vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n + 1, 1);
  for (int i : code) degree[i]++;

  set<int> leaves;
  for (int i = 1; i <= n; i++)
    if (degree[i] == 1) leaves.insert(i);

  vector<pair<int, int>> edges;
  for (int v : code) {
    int leaf = *leaves.begin();
    leaves.erase(leaves.begin());

    edges.emplace_back(leaf, v);
    if (--degree[v] == 1) leaves.insert(v);
  }
  edges.emplace_back(*leaves.begin(), n);
  return edges;
}

signed main() {
  // ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> K;
  for (int i = 0; i <= K; ++i) cin >> a[i];
  for (int i = 0; i <= n; ++i) {
    for (int j = 0, pw = 1; j <= K; ++j, pw = pw * i % MOD)
      C[i] = (C[i] + a[j] * pw) % MOD;
  }
  if (n == 0) {
    cout << 0 << " " << C[0] << "\n";
    return 0;
  }
  if (n == 1) {
    cout << 0 << " " << C[0] << "\n";
    return 0;
  }
  if (n == 2) {
    cout << 1 << " " << C[1] * 2 << "\n";
    cout << 1 << " " << 2 << "\n";
    return 0;
  }
  f[1][1] = C[2] + (n - 1) * C[1];
  for (int i = 1; i < n - 2; ++i) {
    for (int j = 1; j <= i; ++j) {
      if (chkmax(f[i + 1][j + 1], f[i][j] + C[j + 2] - C[j + 1])) h[i + 1][j + 1] = j;
      if (chkmax(f[i + 1][1], f[i][j] + C[2] - C[1])) h[i + 1][1] = j;
    }
  }
  int maxx = 1;
  for (int i = 2; i <= n - 2; ++i) if (f[n - 2][i] > f[n - 2][maxx]) maxx = i;
  cout << n - 1 << " " << f[n - 2][maxx] << "\n";
  dfs(n, maxx, 1);
  auto edges = pruefer_decode(vector<int>(prufer + 1, prufer + n - 2 + 1));
  for (auto it : edges) cout << it.first << " " << it.second << "\n";
  return 0;
}