#include <vector>
#include <cstdio>

using namespace std;

const int INF  = (1 << 30);
const int NMAX = 4096;

int d[2][NMAX+2];
short int v[NMAX+2];
bool r[NMAX+2][NMAX+2];
int N, C;
vector <unsigned short int> sol;

int main() {
    freopen( "conserve.in" , "r" , stdin );
    freopen( "conserve.out" , "w" , stdout );

    for( register int i = 0;  i <= NMAX;  ++i )  d[0][i] = -INF;
    d[0][0] = 0;
    int ind = 1;

    scanf( "%d%d" , &N,&C );
    for( register short int i = 1;  i <= C;  ++i, ind = 1 - ind ) {
        for( register short int j = 0;  j <= NMAX;  ++j )  d[ind][j] = -INF;

        int nr;
        scanf( "%d", &v[i] );
        nr = v[i];

        for( register short int k = 0;  k < N;  ++k ) {
            if( d[1 - ind][k] == -INF )  continue;

            if( d[1 - ind][k] > d[ind][k] ) {
                d[ind][k] = d[1 - ind][k];
                r[i][k] = 0;
            }

            int nk = (k + nr) % N;

            if( d[1 - ind][k] + nr > d[ind][ nk ] ) {
                d[ind][nk] = d[1 - ind][k] + nr;
                r[i][nk] = 1;
            }
        }
    }

    printf( "%d\n" , d[1-ind][0] );

    int rest = 0;
    for( register short int i = C;  i >= 1;  --i ) {
        if( r[i][rest] )  sol.push_back( i );
        ind = 0;
        if( r[i][rest] )  ind = i;

        rest = ( rest - ( v[ind] % N ) + N ) % N;
    }

    printf( "%d\n" , (int)sol.size() );
    for( register short int i = (int)sol.size() - 1;  i >= 0;  --i ) printf( "%u " , sol[i] );

    return 0;
}