//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
//#pra gma G CC opti mize(3)
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x ) {
		if(x==0){
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x ,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
int f[3002][3002],v[3002],g[3002][3002];
int n,k,a[3002];
inline bool ck(int &x,int y){
	if(x<y){
		x=y;
		return true;
	}
	return false;
}
inline void solve(int l,int r,int num,int to){
	if(num==1&&to){
		write(r,' ');
		write(to,'\n');
	}
	if(l==r)return;
	int pos=g[r-l+1][num];
	if(num==1)solve(l,r-1,pos,r);
	else{
		solve(r-pos+1,r,1,to);
		solve(l,r-pos,num-1,to);
	}
}
int main(){
	cin>>n>>k;
	F(i,0,k){
		read(a[i]);
	}
	F(i,1,n){
		UF(j,k,0){
			v[i]=(1ll*v[i]*i+a[j])%59393;
		}
	}
	if(n==1){
		cout<<0<<" "<<v[0]<<endl;
		return 0;
	}
	memset(f,-0x3f,sizeof(f));
	f[1][1]=v[1];
	F(i,1,n){
		F(j,1,i)if(ck(f[i][1],f[i-1][j]+v[j+(i!=n)]))g[i][1]=j;
		F(j,2,i){
			F(k,1,i/j){
				if(ck(f[i][j],f[k][1]+f[i-k][j-1]))g[i][j]=k;
			}
		}
	}
	write(n-1,' ');
	write(f[n][1],'\n');
	solve(1,n,1,0);
    return 0;
}