#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500005;
const int team = 6;
struct Player {
ll k;
int dur, id;
void olvas(int i) {
id = i;
cin>>k>>dur;
}
const bool operator< (Player masik) const {
return k > masik.k;
}
};
Player tab[maxn];
int fin[maxn * team];
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>m>>n;
for(int i=0;i<n;i++) {
tab[i].olvas(i);
}
sort(tab,tab+n);
int it = 0;
int ben = 0;
ll summa = 0LL;
for(int i=0;i<team*m;i++) {
fin[i] = tab[it].id;
summa += tab[it].k;
ben++;
if(ben == tab[it].dur) {
ben = 0;
it++;
}
}
cout<<summa<<endl;
for(int i=0;i<team;i++) {
cout<<fin[ i*m ]+1<<" ";
}
cout<<endl;
int db = 0;
for(int j=1;j<m;j++) {
set<int> le;
set<int> fel;
for(int i=0;i<team;i++) {
if(fin[i*m + j - 1] != fin[i*m + j]) {
le.insert(fin[i*m + j - 1]);
fel.insert(fin[i*m + j]);
}
}
set<int> lec = le;
for(int d:lec) {
if(le.count(d) == 1 && fel.count(d)==1) {
le.erase(d);
fel.erase(d);
}
}
db += le.size();
}
cout<<db<<endl;
for(int j=1;j<m;j++) {
set<int> le;
set<int> fel;
for(int i=0;i<team;i++) {
if(fin[i*m + j - 1] != fin[i*m + j]) {
le.insert(fin[i*m + j - 1]);
fel.insert(fin[i*m + j]);
}
}
set<int> lec = le;
for(int d:lec) {
if(le.count(d) == 1 && fel.count(d)==1) {
le.erase(d);
fel.erase(d);
}
}
auto itle = le.begin();
auto itfel = fel.begin();
while(itle != le.end() && itfel != fel.end()) {
cout<<j<<" "<< *itle + 1 << " " << *itfel + 1 << endl;
itle++;
itfel++;
}
}
return 0;
}
