#P18201. Sub Brackets

Sub Brackets

Sub Brackets

满足以下任意一种情形的字符串称为合法括号序列:

  • 空字符串;
  • 对于某个合法括号序列 ss,依次拼接 (、ss、) 得到的字符串;
  • 对于两个非空的合法括号序列 s,ts,t,将它们拼接得到的字符串。

考虑一个长度为 NN、仅由 ( 和 ) 组成的字符串 SS。给定 MM 条条件,第 ii 条条件要求:

  • SS 从第 LiL_i 个字符到第 RiR_i 个字符组成的连续子串,是合法括号序列。

你可以自由选择 SS。求最多能同时满足多少条条件。

SS 整体不要求是合法括号序列。相同的条件可以重复出现,每一条都分别计数。

输入格式

N M
L_1 R_1
...
L_M R_M

所有输入均为整数,满足:

  • 2≤N≤5002\le N\le500;
  • 1≤M≤5001\le M\le500;
  • 1≤Li<Ri≤N1\le L_i<R_i\le N;
  • Ri−Li+1R_i-L_i+1 为偶数。

输入只有一组数据。

输出格式

输出一个整数,表示最多能同时满足的条件数。

样例 1

输入

5 3
1 2
4 5
2 5

输出

2

说明

选择 S=(()()S=\texttt{(()()},第一条条件不满足,第二、三条满足。无法同时满足全部三条,所以答案为 22。

样例 2

输入

2 4
1 2
1 2
1 2
1 2

输出

4

样例 3

输入

32 11
25 32
19 32
11 24
20 31
22 25
21 26
17 22
30 31
23 28
4 15
19 22

输出

8