Tamem 大楼的电梯

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

一栋楼有 $N$ 层，编号为 $1$ 到 $N$，楼内有三部电梯。你需要提前规划未来 $Q$ 天的电梯移动。

初始时，三部电梯都位于第 $1$ 层且均处于开启状态。每天发生以下一种事件：

• 1 x y：一名乘客需要从第 $x$ 层前往第 $y$ 层。必须由当天开启的一部电梯先到达 $x$，再把乘客送到 $y$；
• 2 p：第 $p$ 部电梯在当天开始时切换开关状态。关闭的电梯当天不能移动，重新开启的电梯当天即可移动。

第 $i$ 天每移动一层的费用为 $A_i$。在不违反开关状态的前提下，你可以在一天中的任意时刻移动任意开启的电梯，也可以让没有载客的电梯提前移动。已知全部事件和费用，请求出满足所有乘客需求的最小总费用。最后无需让电梯返回第 $1$ 层。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含 $Q$ 个整数 $A_1,A_2,\ldots,A_Q$。

接下来 $Q$ 行按时间顺序给出每天的事件，格式为 1 x y 或 2 p。保证任意时刻至少有一部电梯开启。

输出格式

输出一个整数，表示最小总费用。

样例输入

9 8
3 4 4 3 4 2 7 6
1 2 7
1 3 9
2 2
1 4 5
1 3 5
2 2
1 7 3
1 2 1

样例输出

114

数据范围

$2\le N\le10^5$，$1\le Q\le300$，$1\le A_i\le10^5$；乘客事件满足 $1\le x,y\le N$ 且 $x\ne y$。

各子任务数据彼此独立计分。