AT_scpc2026_div2_h CUBRID HA Load Balance

#### 表示言語 / / A CUBRID HA cluster is a system consisting of $ N $ servers. The servers are numbered from $ 1 $ to $ N $ . Jank has become the server administrator of SCSC and wants to choose some of the servers in the CUBRID HA cluster to use. Jank turns on the servers he chooses and turns off the servers he does not choose. Jank, who rules SCSC, chooses whether each chosen server operates as a Master or as a Slave when turning it on. A Master server can process RW requests and RO requests, and a Slave server can process RO requests and SO requests. Each server can process at most one request at the same time. If there is no Master server among the currently turned-on servers and at least one Slave server is currently turned on, the currently turned-on Slave server with the smallest number immediately becomes a Master server. Jank, who rules SCSC, must process $ Q $ queries of the following two types in order. - `1 i`: Turn off server $ i $ . If it is already turned off, ignore this query. - `2 a b c`: $ a $ RW requests, $ b $ RO requests, and $ c $ SO requests arrive simultaneously. The requests that arrive in a type- $ 2 $ query must all be processed using only the servers that are currently turned on. Each request must be assigned to a server that can process that request, and at most one request can be assigned to each server. A request that is not assigned when the query is given cannot be processed. When all requests have been assigned, each server processes its assigned request and discards the processed request. A server with no remaining request becomes ready to process another request again. Find the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output `-1` instead.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is in one of the following two formats: > 1 $ i $ > 2 $ a $ $ b $ $ c $

Output the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output `-1` instead.

### Constraints - $ 1 \leq N,Q \leq 2\,000 $ - $ 1 \leq i \leq N $ - $ 0 \leq a,b,c \leq N $ - There is at least one query of the second type. - All input values are integers.