CF1866E Elevators of Tamem

有一栋名为 Taman Membeku（简称 Tamem）的建筑。这栋建筑共有 $N$ 层，从下到上依次编号为 $1$ 到 $N$。在这栋建筑中，唯一可以在楼层间移动的方式是使用电梯。Tamem 内共有 $3$ 部电梯，分别编号为 $1$、$2$ 和 $3$。 Pak Chanek 是 Tamem 的电梯操作员。他将在 Tamem 工作 $Q$ 天。最初，每部电梯都在第 $1$ 层，并且所有电梯都处于开启状态。在每一天，恰好会发生以下两种事件之一： - 1 x y —— 当前有一人在第 $x$ 层，想要前往第 $y$ 层（$1\leq x,y\leq N$，且 $x\neq y$）。 - 2 p —— 第 $p$ 号电梯在当天开始时改变状态。如果之前是开启，则变为关闭；如果之前是关闭，则变为开启（$1\leq p\leq 3$）。 对于每一天，Pak Chanek 可以随意控制所有电梯的移动。然而，对于每一天中有人在第 $x$ 层想要前往第 $y$ 层的情况，Pak Chanek 所有的电梯操作中，必须满足以下流程： 1. 有一部电梯移动到第 $x$ 层。 2. 该人进入电梯。 3. 该电梯移动到第 $y$ 层。 4. 该人离开电梯。 每天，Pak Chanek 只能操作当前处于开启状态的电梯。注意，电梯状态的变化发生在当天开始时，这意味着某部电梯在某天关闭后，从当天起就无法使用；反之，某部电梯在某天开启后，从当天起即可使用。 已知每天的电费不同。具体来说，第 $j$ 天，每移动一部电梯上下 $1$ 层需要的电费为 $A_j$。 Pak Chanek 事先已经知道所有天的电费和事件顺序，因此他可以有策略地操作电梯。请问，为了满足所有人的需求，最小的总电费是多少？注意，最后每部电梯不需要回到第 $1$ 层。

第一行包含两个整数 $N$ 和 $Q$（$2\leq N\leq 10^5$，$1\leq Q\leq 300$），分别表示楼层数和天数。 第二行包含 $Q$ 个整数 $A_1, A_2, \ldots, A_Q$（$1\leq A_j\leq 10^5$），表示每天每移动一层所需的电费。 接下来的 $Q$ 行，每行描述一天的事件，如下所述。在任何时刻，至少有一部电梯处于开启状态。

输出一个整数，表示满足所有需求所需的最小总电费。

以下是一个最优策略的示例： 1. 第 $1$ 天： - 电梯 $2$ 移动到第 $3$ 层。 - 电梯 $3$ 移动到第 $2$ 层，接上乘客后移动到第 $7$ 层，然后乘客下电梯。 2. 第 $2$ 天： - 电梯 $2$ 接上乘客后移动到第 $9$ 层，然后乘客下电梯。 3. 第 $3$ 天： - 电梯 $2$ 关闭。 4. 第 $4$ 天： - 电梯 $3$ 移动到第 $4$ 层，接上乘客后移动到第 $5$ 层，乘客下电梯，然后移动到第 $3$ 层。 5. 第 $5$ 天： - 电梯 $3$ 接上乘客后移动到第 $5$ 层，然后乘客下电梯。 6. 第 $6$ 天： - 电梯 $2$ 开启。 - 电梯 $1$ 移动到第 $2$ 层。 - 电梯 $2$ 移动到第 $7$ 层。 7. 第 $7$ 天： - 电梯 $2$ 接上乘客后移动到第 $3$ 层，然后乘客下电梯。 8. 第 $8$ 天： - 电梯 $1$ 接上乘客后移动到第 $1$ 层，然后乘客下电梯。 第 $1$ 天到第 $8$ 天的每日电费分别为 $24$、$24$、$0$、$18$、$8$、$6$、$28$ 和 $6$。因此，总电费为 $24+24+0+18+8+6+28+6=114$。 可以证明，没有比这更小的总电费的策略。 由 ChatGPT 4.1 翻译