#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror=0;
inline char nc()
{
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	if (p1==pend)
	{
		p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
		if (pend==p1) {IOerror=1; return -1;}
	}
	return *p1++;
}
inline bool blank(char ch) {return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline ll read()
{
	bool sign=0; char ch=nc(); ll x=0;
	for (; blank(ch); ch=nc());
	if (IOerror)return 0;
	if (ch=='-')sign=1,ch=nc();
	for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
	if (sign)x=-x;
	return x;
}
#undef BUF_SIZE
};
using namespace fastIO;
#define mod 59393
int a[1000010],w[1000010],f[1000010],pre[1000010];
vector<int>v;
vector<pair<int, int>> pruefer_decode(vector<int> const& code)
{
	int n = code.size() + 2;
	vector<int> degree(n, 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 - 1);
	return edges;
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n=qr,k=qr;
	for(int i=0; i<=k; i++)
	{
		in(a[i]);
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=k; j>=1; j--)
		{
			w[i]+=a[j];
			w[i]*=i;
			w[i]%=mod;
		}
		w[i]+=a[0];
		w[i]%=mod;
	}
	memset(f,128,sizeof(f));
	f[0]=w[1]*n;
	for(int i=1; i<=n-2; i++)
	{
		for(int j=i; j<=n-2; j++)
		{
			if(f[j-i]+w[i+1]-w[1]>f[j])f[j]=f[j-i]+w[i+1]-w[1],pre[j]=i;
		}
	}
	int now=n-2,i=0;
	while(now)
	{
		// cout<<pre[now]<<'\n';
		i++;
		for(int j=1; j<=pre[now]; j++)v.push_back(i);
		now-=pre[now];
		// cout<<now<<'\n';
	}
	// for(auto i:v)cout<<i<<' ';cout<<'\n';
	auto e=pruefer_decode(v);
	cout<<n-1<<' '<<f[n-2]<<'\n';
	for(auto i:e)cout<<i.first<<' '<<i.second<<'\n';
	return 0;
}