← 返回题目列表

AtCoder · tupc2023_p

P. 副支架

中文机器翻译题面 查看原题

配点 : {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