CF1132C Painting the Fence

你有一段很长的栅栏，共有 $n$ 段。遗憾的是，这段栅栏还没有被粉刷，于是你决定雇佣 $q$ 个油漆工来粉刷它。第 $i$ 个油漆工会粉刷所有满足 $l_i \le x \le r_i$ 的区段 $x$。 但由于预算有限，你最多只能雇佣 $q-2$ 个油漆工。显然，只有被雇佣的油漆工才会工作。 你希望通过最优地选择 $q-2$ 个油漆工，使得被粉刷的区段数最大。如果某个区段至少被一个油漆工粉刷过，则认为该区段被粉刷。

第一行包含两个整数 $n$ 和 $q$（$3 \le n, q \le 5000$），分别表示栅栏的区段数和可雇佣的油漆工数量。 接下来有 $q$ 行，每行描述一个油漆工：第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）。

输出一个整数，表示在最优选择 $q-2$ 个油漆工的情况下，最多能被粉刷的区段数。

由 ChatGPT 4.1 翻译