配点 : {100} 点
問題文
长度
小于或等于 N 可以得到第 (,) 由……组成的字符串 S 。
下面 M 条件
找出 i \ (1 \leq i \leq M)中可以满足的最大条件数。
- 条件 i : S 可以得到第 L_i 从第一个字符开始 R_i 提取到第一个字符的字符串是带有匹配括号的字符串。
这里,具有匹配括号的字符串被定义为满足以下条件之一的字符串。
- 空文字列
- 带有匹配括号的非空字符串 s,t 存在并且 满足s,t 按此顺序连接而成的字符串
- 带有匹配括号的字符串 s 存在并且
满足
(, s,)按此顺序连接而成的字符串
制約
- 2 \leq N \leq 500
- 1 \leq M \leq 500
- 1 \leq L_i < R_i \leq N \ (1 \leq i \leq M)
- R_i - L_i + 1 是偶数
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
出力
打印答案。 来自
入力例 1
5 3 1 2 4 5 2 5
出力例 1
2
S= (()() 时,1 虽然不满足第一个条件, 2 眼睛和 3 满足第一个条件。
3 同时满足两个条件 S 不存在,所以可以满足的条件是 2 是最大值。
S 本身不需要是带有匹配括号的字符串。
入力例 2
2 4 1 2 1 2 1 2 1 2
出力例 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
出力例 3
8