AT_scpc2026_div2_h CUBRID HA Load Balance

/ / CUBRID HA 集群是由 $N$ 台服务器组成的系统。服务器从 $1$ 到 $N$ 编号。 Jank 成为了 SCSC 的服务器管理员，他想要在 CUBRID HA 集群中选择一些服务器来使用。对于选中的服务器，Jank 会将其打开；没有被选中的服务器则保持关闭状态。 作为 SCSC 的统治者，Jank 会在打开服务器时，为每台选中的服务器选择其工作模式：Master 或 Slave。Master 服务器可以处理 RW 和 RO 请求，Slave 服务器可以处理 RO 和 SO 请求。每台服务器同一时刻最多只能处理一个请求。 如果目前已打开的服务器中没有 Master 服务器，并且至少有一台 Slave 服务器已打开，则编号最小的已打开 Slave 服务器会立即自动变为 Master 服务器。 Jank 需要依次处理 $Q$ 个如下类型的操作： - `1 i`: 关闭编号为 $i$ 的服务器。如果该服务器已关闭，则忽略该操作。 - `2 a b c`: 同时有 $a$ 个 RW 请求、$b$ 个 RO 请求、$c$ 个 SO 请求到达。 对于每个类型为 $2$ 的操作，必须仅使用当前已打开的服务器来处理所有请求。每个请求都必须分配给能够处理该请求的服务器，并且每台服务器至多只能分配一个请求。如果某个请求无法分配，在该次操作中将无法被处理。 所有请求分配完毕后，每台服务器处理其分配到的请求，处理完即被清除。没有处理请求的服务器会再次准备好处理新的请求。 请你计算，Jank 至少需要在一开始选择多少台服务器，才能处理全部请求。如果无论如何都无法处理所有请求，请输出 `-1`。

输入从标准输入读入，格式如下： > $N\ Q$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个操作有以下两种形式之一： > 1 $i$ > 2 $a\ b\ c$

输出一个整数，表示 Jank 最少需要在一开始选择多少台服务器，才能处理全部请求。如果无法处理所有请求，则输出 `-1`。

### 数据范围 - $1 \leq N,Q \leq 2\,000$ - $1 \leq i \leq N$ - $0 \leq a,b,c \leq N$ - 保证至少有一条类型为 2 的操作。 - 所有输入均为整数。 由 ChatGPT 5 翻译