AT_scpc2026_div2_h CUBRID HA Load Balance

#### 表示言語 / / CUBRID HA クラスタは $ N $ 台のサーバからなるシステムです．サーバには $ 1 $ 番から $ N $ 番までの番号が付いています． SCSC のサーバ管理者に就任した Jank は，CUBRID HA クラスタのサーバのうちいくつかを選んで使おうとしています．Jank は選んだサーバを起動し，選ばないサーバを停止します． SCSC を支配する Jank は，選んだ各サーバを起動するとき，Master または Slave のどちらとして動作させるかを選びます．Master サーバは RW リクエストと RO リクエストを処理でき，Slave サーバは RO リクエストと SO リクエストを処理できます．各サーバは同時に高々 $ 1 $ 個のリクエストしか処理できません． 現在起動しているサーバの中に Master サーバが $ 1 $ 台も存在せず，現在起動している Slave サーバが $ 1 $ 台以上存在する場合，現在起動している Slave サーバのうち番号が最も小さいサーバがただちに Master サーバになります． SCSC を支配する Jank は，以下の $ 2 $ 種類のクエリを $ Q $ 個，順に処理しなければなりません． - `1 i`: サーバ $ i $ を停止する．すでに停止しているサーバなら無視する． - `2 a b c`: RW リクエスト $ a $ 個，RO リクエスト $ b $ 個，SO リクエスト $ c $ 個が同時に到着する． $ 2 $ 番目の形式のクエリで到着したリクエストは，現在起動しているサーバだけを使ってすべて処理しなければなりません．各リクエストは，そのリクエストを処理できるサーバに割り当てる必要があり， $ 1 $ 台のサーバには高々 $ 1 $ 個のリクエストしか割り当てられません．クエリが与えられた時点で割り当てられなかったリクエストは処理できません． すべてのリクエストが割り当てられると，各サーバはリクエストを処理し，処理したリクエストを破棄します．残っているリクエストがないサーバは，再び他のリクエストを処理できる状態になります． SCSC を支配する Jank がすべてのリクエストを処理するためには，最初に選ぶ必要があるサーバの最小個数を求めてください．どのような方法でもすべてのリクエストを処理できない場合は，代わりに `-1` を出力してください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の $ 2 $ 種類のいずれかの形式で与えられる． > 1 $ i $ > 2 $ a $ $ b $ $ c $

SCSC を支配する Jank がすべてのリクエストを処理するために最初に選ぶ必要があるサーバの最小個数を出力せよ．どのような方法でもすべてのリクエストを処理できない場合は，代わりに `-1` を出力せよ．

### Constraints - $ 1 \leq N,Q \leq 2\,000 $ - $ 1 \leq i \leq N $ - $ 0 \leq a,b,c \leq N $ - $ 2 $ 番目の形式のクエリが少なくとも $ 1 $ 個与えられる - 入力される数値はすべて整数