#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[500], b[500], c[500];
int main() {
  cin >> n >> m;
  int ma = -(int)1e9 + 7, mi = (int)1e9 + 7;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ma = max(ma, a[i]);
    mi = min(mi, a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> b[i] >> c[i];
  }
  int tp = ma - mi;
  int cnt[500];
  vector<int> ans;
  for (int i = 1; i <= n; ++i) {
    ma = -(int)1e9 + 7, mi = (int)1e9 + 7;
    memset(cnt, 0, sizeof(cnt));
    vector<int> t;
    for (int j = 1; j <= m; ++j)
      if ((b[j] <= i) && (i <= c[j])) {
        t.push_back(j);
        cnt[b[j]]--;
        cnt[c[j] + 1]++;
      }
    for (int j = 1; j <= n; ++j) cnt[j] += cnt[j - 1];
    for (int j = 1; j <= n; ++j) {
      ma = max(ma, a[j] + cnt[j]);
      mi = min(mi, a[j] + cnt[j]);
    }
    if ((ma - mi) > tp) {
      tp = ma - mi;
      while (!ans.empty()) ans.pop_back();
      for (int j = 0; j < (int)(t).size(); ++j) ans.push_back(t[j]);
    }
  }
  cout << tp << endl;
  cout << ans.size() << endl;
  for (int i = 0; i < (int)(ans).size(); ++i) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
