#define poj
#define zcz
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<random>
#include<set>
#include<stack>
#include<string>
#include<vector>
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *inf;
	char *inbuf,*inst,*ined;
	inline char _getchar(){
		if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
		return inst==ined?EOF:*inst++;
	}
	public:
	fastin(FILE*_inf=stdin){
		inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
	}
	~fastin(){delete inbuf;}
	template<typename Int> fastin&operator>>(Int &n){
		static char c;
		Int t=1;
		while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
		n=(c^48);
		while((c=_getchar())>='0'&&c<='9')n=(n<<3)+(n<<1)+(c^48);
		n*=t;
		return *this;
	}
	fastin&operator>>(char*s){
		int t=0;
		static char c;
		while((c=_getchar())!=' '&&c!='\n')s[t++]=c;
		s[t]='\0';
		return *this;
	}
}fi;
class fastout{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *ouf;
	char *oubuf,*oust,*oued;
	inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
	inline void _putchar(char c){
		if(oued==oust+MAXBF)_flush(),oued=oubuf;
		*oued++=c;
	}
	public:
	fastout(FILE*_ouf=stdout){
		oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
	}
	~fastout(){_flush();delete oubuf;}
	template<typename Int> fastout&operator<<(Int n){
		if(n<0)_putchar('-'),n=-n;
		static char S[20];
		int t=0;
		do{S[t++]='0'+n%10,n/=10;}while(n);
		for(int i=0;i<t;++i)_putchar(S[t-i-1]);
		return *this;
	}
	fastout&operator<<(char c){_putchar(c);return *this;}
	fastout&operator<<(char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
	fastout&operator<<(const char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod 59393
#define ll long long
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define next ___
int n,k,a[15],t[3010],dp[3010],fr[3010],g[3010],cnt,p;
void dfs(int x){for(int i=1;i<=g[x];++i)cout<<++p<<' '<<x<<'\n',dfs(p);}
void solve(){
	cin>>n>>k;
	for(int i=0;i<=k;++i)cin>>a[i];
	for(int i=0;i<=n;++i)for(int j=k;~j;--j)t[i]=(t[i]*i%mod+a[j])%mod;
	if(n==1){cout<<0<<' '<<t[0];return;}
	if(n==2){cout<<1<<' '<<2*t[1]%mod<<'\n'<<1<<' '<<2;return;}
	dp[0]=n*t[1];
	for(int i=1;i<=n;++i)
		for(int j=i-1;j<n-1;++j)
			if(dp[j]<dp[j-i+1]+t[i]-t[1]){
				dp[j]=dp[j-i+1]+t[i]-t[1];
				fr[j]=j-i+1;
			}
	cout<<n-1<<' '<<dp[n-2]<<'\n';
	for(int i=n-2;i;i=fr[i])g[++cnt]=i-fr[i];
	sort(g+1,g+1+cnt);++g[1];
	p=1;dfs(1);
	return;
}
int main(){
	timespec time1={0,0};
	clock_gettime(CLOCK_REALTIME,&time1);
	#ifndef zcz
	czc;
	#endif
	int t=1;
	while(t--)solve();
	timespec time2={0,0};
	clock_gettime(CLOCK_REALTIME,&time2);
	while(1000000000ll*(time2.tv_sec-time1.tv_sec)+1ll*(time2.tv_nsec-time1.tv_nsec)<998000000ll)clock_gettime(CLOCK_REALTIME,&time2);
	return 0;
}