CF1866E.Elevators of Tamem

There is a building named Taman Membeku (shortened as Tamem). The building has $N$ floors numbered from $1$ to $N$ from bottom to top. The only way to move between floors in the building is to use elevators. There are $3$ elevators available in Tamem, namely elevators $1$, $2$, and $3$.

Pak Chanek works as an elevator operator in Tamem. Pak Chanek will work for $Q$ days. Initially, each elevator is in floor $1$ and all elevators are on. On each day, exactly one of the following will happen:

• 1 x y – There is a person currently in floor $x$ who wants to go to floor $y$. ($1\leq x,y\leq N$; $x\neq y$)
• 2 p – Elevator $p$ changes state at the start of the day. If previously it is on, then it will turn off. If previously it is off, then it will turn on. ($1\leq p\leq3$)

For each day, Pak Chanek can control the movement of all elevators as he pleases. However, for each day where there is a person currently in floor $x$ who wants to go to floor $y$, among all elevator movements done by Pak Chanek, the following must happen:

1. One elevator moves to floor $x$.
2. The person gets into the elevator.
3. The elevator moves to floor $y$.
4. The person gets out of the elevator.

For each day, Pak Chanek can only move the elevators that are currently on. Note that, since a change in state happens at the start of the day, this means that an elevator that turns off on some day starts becoming unusable from that day itself. Conversely, an elevator that turns on on some day starts becoming usable from that day itself.

It is known that the electricity fee for each day is different. More specifically, on the $j$-th day, the fee needed to move one elevator up or down by one floor is $A_j$.

From the start, Pak Chanek already knows the electricity fees and the sequence of events that will happen on the $Q$ days, so Pak Chanek can operate the elevators strategically. What is the minimum possible electricity fee to fulfill all needs of the people who want to move between floors in Tamem? Note: in the end, each elevator does not have to go back to floor $1$.

有一栋名为“Taman Membeku”（简称 Tamem）的大楼。该大楼共有 $N$ 层，自下而上编号为 $1$ 至 $N$。大楼内楼层之间唯一的通行方式是乘坐电梯。Tamem 大楼内共有 $3$ 部电梯，分别称为电梯 $1$、电梯 $2$ 和电梯 $3$。

Pak Chanek 是 Tamem 大楼的一名电梯操作员。他将连续工作 $Q$ 天。初始时，每部电梯均位于第 $1$ 层，且全部处于开启状态。每天恰好发生以下两种事件之一：

• 1 x y —— 当前有一个人在第 $x$ 层，希望前往第 $y$ 层。（$1\leq x,y\leq N$；$x\neq y$）
• 2 p —— 在当天开始时，电梯 $p$ 的开关状态发生切换：若之前处于开启状态，则变为关闭；若之前处于关闭状态，则变为开启。（$1\leq p\leq3$）

每天 Pak Chanek 均可自由控制所有电梯的运行。但若当天发生了“有一个人在第 $x$ 层希望前往第 $y$ 层”的事件，则 Pak Chanek 所进行的所有电梯移动中，必须满足以下过程：

1. 某一部电梯移动至第 $x$ 层；
2. 该人进入该电梯；
3. 该电梯从第 $x$ 层移动至第 $y$ 层；
4. 该人离开该电梯。

此外，每天 Pak Chanek 只能移动当前处于开启状态的电梯。注意：由于状态切换发生在当天开始时，因此某天被关闭的电梯从当天起即不可用；反之，某天被开启的电梯也从当天起即可使用。

已知每天的电费各不相同。具体而言，在第 $j$ 天，使一部电梯向上或向下移动一层所需的电费为 $A_j$。

从一开始，Pak Chanek 就已知晓全部 $Q$ 天的电费序列及每日发生的事件序列，因此他可以战略性地调度电梯。问：为满足 Tamem 大楼中所有人员的楼层间通行需求，所需支付的最小总电费是多少？
注：最终，各电梯无需返回第 $1$ 层。

The first line contains two integers $N$ and $Q$ ($2\leq N\leq10^5$; $1\leq Q\leq300$) — the number of floors and the number of days.

The second line contains $Q$ integers $A_1, A_2, A_3 \ldots, A_Q$ ($1 \leq A_j \leq 10^5$) — the electricity fee for each day.

The $j$-th of the next $Q$ lines contains the $j$-th event as described. At any moment, there will always be at least one elevator that is on.

第一行包含两个整数 $N$ 和 $Q$（$2\leq N\leq10^5$；$1\leq Q\leq300$）——分别为楼层数与天数。

第二行包含 $Q$ 个整数 $A_1, A_2, A_3 \ldots, A_Q$（$1 \leq A_j \leq 10^5$）——表示每一天的电费。

接下来的 $Q$ 行中，第 $j$ 行描述第 $j$ 个事件。在任意时刻，总至少有一部电梯处于运行状态。

An integer representing the minimum possible electricity fee to fulfill all needs of the people who want to move between floors in Tamem.

一个整数，表示满足塔梅姆所有人员楼层间移动需求所需的最低电费。

The following is an example of an optimal strategy:

1. On the $1$-st day:
   • Elevator $2$ moves to floor $3$.
   • Elevator $3$ moves to floor $2$, picks the person up, moves to floor $7$, then drops the person off.
2. On the $2$-nd day:
   • Elevator $2$ picks the person up, moves to floor $9$, then drops the person off.
3. On the $3$-rd day:
   • Elevator $2$ turns off.
4. On the $4$-th day:
   • Elevator $3$ moves to floor $4$, picks the person up, moves to floor $5$, drops the person off, then moves to floor $3$.
5. On the $5$-th day:
   • Elevator $3$ picks the person up, moves to floor $5$, then drops the person off.
6. On the $6$-th day:
   • Elevator $2$ turns on.
   • Elevator $1$ moves to floor $2$.
   • Elevator $2$ moves to floor $7$.
7. On the $7$-th day:
   • Elevator $2$ picks the person up, moves to floor $3$, then drops the person off.
8. On the $8$-th day:
   • Elevator $1$ picks the person up, moves to floor $1$, then drops the person off.

The total electricity fee for each day from the $1$-st day to the $8$-th day are $24$, $24$, $0$, $18$, $8$, $6$, $28$, and $6$ respectively. Therefore, the total electricity fee for the entire $Q$ days is $24+24+0+18+8+6+28+6=114$.

It can be obtained that there is no strategy that requires a smaller electricity fee.

以下是最佳策略的一个示例：

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$。因此，整个 $Q$ 天的总电费为 $24+24+0+18+8+6+28+6=114$。

可以证明，不存在所需电费更少的策略。