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.

CUBRID HA 集群是由 $N$ 台服务器组成的系统，服务器编号为 $1$ 至 $N$。

Jank 成为了 SCSC 的服务器管理员，他希望从该 CUBRID HA 集群中选择若干台服务器投入使用。Jank 将开启所选的服务器，而关闭未被选中的服务器。

作为 SCSC 的统治者，Jank 在开启每台被选中的服务器时，还需决定其运行模式：主服务器（Master）或从服务器（Slave）。主服务器可处理读写请求（RW 请求）和只读请求（RO 请求）；从服务器可处理只读请求（RO 请求）和特殊操作请求（SO 请求）。每台服务器同一时刻最多只能处理一个请求。

若当前所有已开启的服务器中没有主服务器，但至少有一台从服务器处于开启状态，则编号最小的已开启从服务器将立即自动升级为主服务器。

作为 SCSC 的统治者，Jank 必须按顺序处理 $Q$ 个如下两类查询：

• 1 i：关闭服务器 $i$。若该服务器当前已是关闭状态，则忽略此查询。
• 2 a b c：同时到达 $a$ 个 RW 请求、$b$ 个 RO 请求和 $c$ 个 SO 请求。

在类型为 2 的查询中到达的所有请求，必须且仅能由当前已开启的服务器进行处理。每个请求必须被分配给一台能够处理该类请求的服务器，且每台服务器至多被分配一个请求。若在该查询发出时存在未被分配的请求，则这些请求无法被处理。

当所有请求均完成分配后，各服务器即开始处理各自被分配的请求，并在处理完成后丢弃该请求。处理完请求后无待处理请求的服务器，将立即恢复为可处理下一个请求的就绪状态。

请找出 Jank（SCSC 的统治者）初始必须选择的最少服务器数量，使得所有请求均可被处理。若无论采用何种方式均无法处理全部请求，则输出 -1。

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$

输入从标准输入中以如下格式给出：

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询为以下两种格式之一：

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.

输出Jank（SCSC的统治者）最初必须选择的服务器的最小数量，以处理所有请求。如果无法通过任何方法处理所有请求，则输出 -1。

表示言語

/ /

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.

表示语言

/ /

限制条件

• $1 \leq N,Q \leq 2\,000$
• $1 \leq i \leq N$
• $0 \leq a,b,c \leq N$
• 至少存在一个类型为二的查询。
• 所有输入值均为整数。