有一座名为 Taman Membeku(简称 Tamem)的建筑物。该建筑有 $$$N$$$ 楼层,从下到上编号为 $$$1$$$ 到 $$$N$$$。在建筑物各楼层之间移动的唯一方法是使用电梯。 Tamem 有 $$$3$$$ 电梯,即电梯 $$$1$$$、$$$2$$$ 和 $$$3$$$。
Pak Chanek 在 Tamem 担任电梯操作员。 Pak Chanek 将工作 $$$Q$$$ 天。最初,每部电梯位于 $$$1$$$ 层,并且所有电梯均已开启。每一天,都会发生以下其中一种情况:
- 1 x y – 目前在 $$$x$$$ 楼层有人想要前往 $$$y$$$ 楼层。 ($$$1\leq x,y\leq N$$$; $$$x\neq y$$$)
- 下午 2 点 – 电梯 $$$p$$$ 在一天开始时更改状态。如果之前它是打开的,那么它将关闭。如果之前它是关闭的,那么它将打开。 ($$$1\leq p\leq3$$$)
Pak Chanek 每天都可以随心所欲地控制所有电梯的运行。然而,对于当前位于 $$$x$$$ 楼层的每一天,想要前往 $$$y$$$ 楼层的人,在 Pak Chanek 执行的所有电梯移动中,必须发生以下情况:
1. 一部电梯移至 $$$x$$$ 层。
2. 该人进入电梯。
3. 电梯移至楼层 $$$y$$$。
4. 该人走出电梯。
Pak Chanek 每天只能移动当前运行的电梯。请注意,由于状态变化发生在一天开始时,这意味着在某一天关闭的电梯从那天起就开始变得无法使用。相反,某天开启的电梯从那天起就开始可用。
据了解,每天的电费是不同的。更具体地,在第$$$j$$$天,将一部电梯向上或向下移动一层所需的费用为$$$A_j$$$。
从一开始,Pak Chanek 就已经知道电费以及 $$$Q$$$ 日将发生的事件顺序,因此 Pak Chanek 可以有策略地操作电梯。满足想要在 Tamem 楼层之间移动的人们的所有需求的最低电费是多少?注意:最后每部电梯不必返回$$$1$$$层。
输入
第一行包含两个整数 $$$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$$$ 事件。在任何时刻,总会至少有一部电梯处于运行状态。
输出
一个整数,表示满足想要在 Tamem 楼层之间移动的人员的所有需求的最低可能电费。
示例
输入 #1
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
输出 #1
114
注意
以下是最佳策略的示例:
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$$$。
可以得出,不存在需要更小的电费的策略。