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 $

答えを出力せよ。

### Sample Explanation 1 $ S= $ `(()()` のとき、 $ 1 $ つ目の条件は満たしませんが、 $ 2 $ つ目と $ 3 $ つ目の条件を満たしています。 $ 3 $ つの条件を同時に満たす $ S $ は存在しないため、満たすことのできる条件は $ 2 $ つが最大です。 $ S $ 自身は括弧の対応が取れている文字列である必要はありません。 ### Sample Explanation 2 同じ条件が複数ある場合もあります。 ### Constraints - $ 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 $ は偶数 - 入力はすべて整数