AT_tupc2023_p Sub Brackets

给定一个长度为 $N$ 仅由 `(` 和 `)` 组成的字符串 $S$，现有 $M$ 个条件，对于每个条件 $i\ (1 \leq i \leq M)$，问最多能满足多少个条件。 每个条件 $i$ ：取出 $S$ 的第 $L_i$ 个字符到第 $R_i$ 个字符组成的子串，该子串是一个匹配的括号序列。 这里，匹配的括号序列定义如下： - 空字符串； - 存在两个非空匹配的括号序列 $s, t$，将 $s, t$ 依次连接后得到的字符串； - 存在匹配的括号序列 $s$，则 `(` 、$s$、`)` 依次连接得到的字符串。

输入通过标准输入给出，格式如下： > $N\ M$ > $L_1\ R_1$ > $L_2\ R_2$ > $\vdots$ > $L_M\ R_M$

输出满足条件的最大个数。

### 样例解释 1 当 $S=$ `(()()` 时，第 1 个条件不满足，但第 2、3 个条件满足。 不存在能够同时满足全部 3 个条件的 $S$，因此最多能满足 $2$ 个条件。 注意，$S$ 本身不必是匹配的括号序列。 ### 样例解释 2 条件可能有重复。 ### 数据范围 - $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$ 为偶数 - 输入均为整数 由 ChatGPT 5 翻译