import static java.
lang.
Double.
parseDouble; import static java.
lang.
Integer.
parseInt; import static java.
lang.
Long.
parseLong; import static java.
lang.
Math.
*; import static java.
lang.
System.
exit;
import java.io.*;
import java.util.*;
class Ideone {
class Pair implements Comparable<Pair> {
int r, l;
Pair(int l, int r) {
this.l = l;
this.r = r;
}
@Override
public int compareTo(Pair o) {
return l == o.l ? r - o.r : l - o.l;
}
}
int n, q, dp[][][];
Pair segs[];
int fun(int i,int last, int missed) {
if(i == q) return missed == 2 ? 0 : -n;
if(dp[missed][i][last] != -1) return dp[missed][i][last];
int ans = 0;
if(missed < 2) ans = max(ans, fun(i+1, last, missed + 1));
if(last >= segs[i].l) {
ans = max(ans , max(segs[i].r - last, 0) + fun(i+1, max(last, segs[i].r), missed));
} else {
ans = max(ans , segs[i].r - segs[i].l + 1 + fun(i+1, max(last, segs[i].r), missed));
}
return dp[missed][i][last]=ans;
}
n = nextInt(); q = nextInt();
segs = new Pair[q];
for(int i = 0; i < q; i++) segs[i] = new Pair(nextInt(), nextInt());
dp = new int[3][5010][5010];
for(int i
= 0; i
< 3; i
++) for(int j
= 0; j
< 5010;j
++) Arrays.
fill(dp
[i
][j
],
-1); out.println(fun(0,0,0));
}
// call it like this: lower_bound(a, x + 1) ( /!\ + 1 )
public static int lower_bound(int[] a, int v) {
int low = -1, high = a.length;
while (high - low > 1) {
int h = high + low >>> 1;
if (a[h] >= v) {
high = h;
} else {
low = h;
}
}
return high;
}
private int gcd(int a, int b) {
while (b > 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
private int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
public static int[] radixSort(int[] f) {
int[] to = new int[f.length];
{
int[] b = new int[65537];
for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
int[] d = f;
f = to;
to = d;
}
{
int[] b = new int[65537];
for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
int[] d = f;
f = to;
to = d;
}
return f;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}
return parseInt(next());
}
return parseLong(next());
}
return parseDouble(next());
}
while (tok == null || !tok.hasMoreTokens()) {
}
return tok.nextToken();
}
try {
//long lStartTime = System.currentTimeMillis();
new Ideone().solve();
//long lEndTime = System.currentTimeMillis();
//out.println("Elapsed time in seconds: " + (double)(lEndTime - lStartTime) / 1000.0);
in.close();
out.close();
e.printStackTrace();
exit(1);
}
}
}
aW1wb3J0IHN0YXRpYyBqYXZhLmxhbmcuRG91YmxlLnBhcnNlRG91YmxlOwppbXBvcnQgc3RhdGljIGphdmEubGFuZy5JbnRlZ2VyLnBhcnNlSW50OwppbXBvcnQgc3RhdGljIGphdmEubGFuZy5Mb25nLnBhcnNlTG9uZzsKaW1wb3J0IHN0YXRpYyBqYXZhLmxhbmcuTWF0aC4qOwppbXBvcnQgc3RhdGljIGphdmEubGFuZy5TeXN0ZW0uZXhpdDsKCmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLnV0aWwuKjsKCiBjbGFzcyBJZGVvbmUgewoKICAgIHN0YXRpYyBCdWZmZXJlZFJlYWRlciBpbjsKICAgIHN0YXRpYyBQcmludFdyaXRlciBvdXQ7CiAgICBzdGF0aWMgU3RyaW5nVG9rZW5pemVyIHRvazsKCgogICAgY2xhc3MgUGFpciBpbXBsZW1lbnRzIENvbXBhcmFibGU8UGFpcj4gewogICAgICAgIGludCByLCBsOwoKICAgICAgICBQYWlyKGludCBsLCBpbnQgcikgewogICAgICAgICAgICB0aGlzLmwgPSBsOwogICAgICAgICAgICB0aGlzLnIgPSByOwogICAgICAgIH0KCiAgICAgICAgQE92ZXJyaWRlCiAgICAgICAgcHVibGljIGludCBjb21wYXJlVG8oUGFpciBvKSB7CiAgICAgICAgICAgIHJldHVybiBsID09IG8ubCA/IHIgLSBvLnIgOiBsIC0gby5sOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgbiwgcSwgZHBbXVtdW107CiAgICBQYWlyIHNlZ3NbXTsKICAgIGludCBmdW4oaW50IGksaW50IGxhc3QsIGludCBtaXNzZWQpIHsKICAgICAgICBpZihpID09IHEpIHJldHVybiBtaXNzZWQgPT0gMiA/IDAgOiAtbjsKICAgICAgICBpZihkcFttaXNzZWRdW2ldW2xhc3RdICE9IC0xKSByZXR1cm4gZHBbbWlzc2VkXVtpXVtsYXN0XTsKICAgICAgICBpbnQgYW5zID0gMDsKICAgICAgICBpZihtaXNzZWQgPCAyKSBhbnMgPSBtYXgoYW5zLCBmdW4oaSsxLCBsYXN0LCBtaXNzZWQgKyAxKSk7CiAgICAgICAgaWYobGFzdCA+PSBzZWdzW2ldLmwpIHsKICAgICAgICAgICAgYW5zID0gbWF4KGFucyAsIG1heChzZWdzW2ldLnIgLSBsYXN0LCAwKSArIGZ1bihpKzEsIG1heChsYXN0LCBzZWdzW2ldLnIpLCBtaXNzZWQpKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBhbnMgPSBtYXgoYW5zICwgc2Vnc1tpXS5yIC0gc2Vnc1tpXS5sICsgMSArIGZ1bihpKzEsIG1heChsYXN0LCBzZWdzW2ldLnIpLCBtaXNzZWQpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGRwW21pc3NlZF1baV1bbGFzdF09YW5zOwogICAgfQoKICAgIHZvaWQgc29sdmUoKSB0aHJvd3MgRXhjZXB0aW9uIHsKICAgICAgICBuID0gbmV4dEludCgpOyBxID0gbmV4dEludCgpOwogICAgICAgIHNlZ3MgPSBuZXcgUGFpcltxXTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgcTsgaSsrKSBzZWdzW2ldID0gbmV3IFBhaXIobmV4dEludCgpLCBuZXh0SW50KCkpOwogICAgICAgIEFycmF5cy5zb3J0KHNlZ3MpOwogICAgICAgIGRwID0gbmV3IGludFszXVs1MDEwXVs1MDEwXTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgMzsgaSsrKSBmb3IoaW50IGo9IDA7IGogPCA1MDEwO2orKykgQXJyYXlzLmZpbGwoZHBbaV1bal0sIC0xKTsKICAgICAgICBvdXQucHJpbnRsbihmdW4oMCwwLDApKTsKICAgIH0KCgogICAgLy8gY2FsbCBpdCBsaWtlIHRoaXM6IGxvd2VyX2JvdW5kKGEsIHggKyAxKSAoIC8hXCArIDEgKQogICAgcHVibGljIHN0YXRpYyBpbnQgbG93ZXJfYm91bmQoaW50W10gYSwgaW50IHYpIHsKICAgICAgICBpbnQgbG93ID0gLTEsIGhpZ2ggPSBhLmxlbmd0aDsKICAgICAgICB3aGlsZSAoaGlnaCAtIGxvdyA+IDEpIHsKICAgICAgICAgICAgaW50IGggPSBoaWdoICsgbG93ID4+PiAxOwogICAgICAgICAgICBpZiAoYVtoXSA+PSB2KSB7CiAgICAgICAgICAgICAgICBoaWdoID0gaDsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGxvdyA9IGg7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGhpZ2g7CiAgICB9CgogICAgcHJpdmF0ZSBpbnQgZ2NkKGludCBhLCBpbnQgYikgewogICAgICAgIHdoaWxlIChiID4gMCkgewogICAgICAgICAgICBpbnQgdGVtcCA9IGI7CiAgICAgICAgICAgIGIgPSBhICUgYjsKICAgICAgICAgICAgYSA9IHRlbXA7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhOwogICAgfQoKICAgIHByaXZhdGUgaW50IGxjbShpbnQgYSwgaW50IGIpIHsKICAgICAgICByZXR1cm4gYSAqIChiIC8gZ2NkKGEsIGIpKTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIGludFtdIHJhZGl4U29ydChpbnRbXSBmKSB7CiAgICAgICAgaW50W10gdG8gPSBuZXcgaW50W2YubGVuZ3RoXTsKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIGIgPSBuZXcgaW50WzY1NTM3XTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBmLmxlbmd0aDsgaSsrKSBiWzEgKyAoZltpXSAmIDB4ZmZmZildKys7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IDY1NTM2OyBpKyspIGJbaV0gKz0gYltpIC0gMV07CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZi5sZW5ndGg7IGkrKykgdG9bYltmW2ldICYgMHhmZmZmXSsrXSA9IGZbaV07CiAgICAgICAgICAgIGludFtdIGQgPSBmOwogICAgICAgICAgICBmID0gdG87CiAgICAgICAgICAgIHRvID0gZDsKICAgICAgICB9CiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBiID0gbmV3IGludFs2NTUzN107CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZi5sZW5ndGg7IGkrKykgYlsxICsgKGZbaV0gPj4+IDE2KV0rKzsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gNjU1MzY7IGkrKykgYltpXSArPSBiW2kgLSAxXTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBmLmxlbmd0aDsgaSsrKSB0b1tiW2ZbaV0gPj4+IDE2XSsrXSA9IGZbaV07CiAgICAgICAgICAgIGludFtdIGQgPSBmOwogICAgICAgICAgICBmID0gdG87CiAgICAgICAgICAgIHRvID0gZDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGY7CiAgICB9CgogICAgcHJpdmF0ZSBpbnRbXSBuYShpbnQgbikgdGhyb3dzIElPRXhjZXB0aW9uIHsKICAgICAgICBpbnRbXSBhID0gbmV3IGludFtuXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgYVtpXSA9IG5leHRJbnQoKTsKICAgICAgICByZXR1cm4gYTsKICAgIH0KCiAgICBwcml2YXRlIGxvbmdbXSBuYWwoaW50IG4pIHRocm93cyBJT0V4Y2VwdGlvbiB7CiAgICAgICAgbG9uZ1tdIGEgPSBuZXcgbG9uZ1tuXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgYVtpXSA9IG5leHRMb25nKCk7CiAgICAgICAgcmV0dXJuIGE7CiAgICB9CgogICAgaW50IG5leHRJbnQoKSB0aHJvd3MgSU9FeGNlcHRpb24gewogICAgICAgIHJldHVybiBwYXJzZUludChuZXh0KCkpOwogICAgfQoKICAgIGxvbmcgbmV4dExvbmcoKSB0aHJvd3MgSU9FeGNlcHRpb24gewogICAgICAgIHJldHVybiBwYXJzZUxvbmcobmV4dCgpKTsKICAgIH0KCiAgICBkb3VibGUgbmV4dERvdWJsZSgpIHRocm93cyBJT0V4Y2VwdGlvbiB7CiAgICAgICAgcmV0dXJuIHBhcnNlRG91YmxlKG5leHQoKSk7CiAgICB9CgogICAgU3RyaW5nIG5leHQoKSB0aHJvd3MgSU9FeGNlcHRpb24gewogICAgICAgIHdoaWxlICh0b2sgPT0gbnVsbCB8fCAhdG9rLmhhc01vcmVUb2tlbnMoKSkgewogICAgICAgICAgICB0b2sgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGluLnJlYWRMaW5lKCkpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gdG9rLm5leHRUb2tlbigpOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewogICAgICAgIHRyeSB7CiAgICAgICAgICAgIGluID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKICAgICAgICAgICAgb3V0ID0gbmV3IFByaW50V3JpdGVyKG5ldyBPdXRwdXRTdHJlYW1Xcml0ZXIoU3lzdGVtLm91dCkpOwogICAgICAgICAgICAvL2xvbmcgbFN0YXJ0VGltZSA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwogICAgICAgICAgICBuZXcgSWRlb25lKCkuc29sdmUoKTsKICAgICAgICAgICAgLy9sb25nIGxFbmRUaW1lID0gU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCk7CiAgICAgICAgICAgIC8vb3V0LnByaW50bG4oIkVsYXBzZWQgdGltZSBpbiBzZWNvbmRzOiAiICsgKGRvdWJsZSkobEVuZFRpbWUgLSBsU3RhcnRUaW1lKSAvIDEwMDAuMCk7CiAgICAgICAgICAgIGluLmNsb3NlKCk7CiAgICAgICAgICAgIG91dC5jbG9zZSgpOwogICAgICAgIH0gY2F0Y2ggKFRocm93YWJsZSBlKSB7CiAgICAgICAgICAgIGUucHJpbnRTdGFja1RyYWNlKCk7CiAgICAgICAgICAgIGV4aXQoMSk7CiAgICAgICAgfQogICAgfQp9