#P18201. Sub Brackets
Sub Brackets
Sub Brackets
满足以下任意一种情形的字符串称为合法括号序列:
- 空字符串;
- 对于某个合法括号序列 ,依次拼接
(、、)得到的字符串; - 对于两个非空的合法括号序列 ,将它们拼接得到的字符串。
考虑一个长度为 、仅由 ( 和 ) 组成的字符串 。给定 条条件,第 条条件要求:
- 从第 个字符到第 个字符组成的连续子串,是合法括号序列。
你可以自由选择 。求最多能同时满足多少条条件。
整体不要求是合法括号序列。相同的条件可以重复出现,每一条都分别计数。
输入格式
N M
L_1 R_1
...
L_M R_M
所有输入均为整数,满足:
- ;
- ;
- ;
- 为偶数。
输入只有一组数据。
输出格式
输出一个整数,表示最多能同时满足的条件数。
样例 1
输入
5 3
1 2
4 5
2 5
输出
2
说明
选择 ,第一条条件不满足,第二、三条满足。无法同时满足全部三条,所以答案为 。
样例 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