描述

开启了升降梯的动力之后,探险队员们进入了升降梯运行的那条竖直的隧道,映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
Nescafé 之塔一共有N 层,升降梯在每层都有一个停靠点。手柄有M 个控制槽,第i个控制槽旁边标着一个数Ci,满足C1<C2<C3<...<CM。如果Ci>0,表示手柄扳动到该槽时,电梯将上升Ci 层;如果Ci<0,表示手柄扳动到该槽时,电梯将下降-Ci 层;并且一定存在一个Ci=0,手柄最初就位于此槽中。注意升降梯只能在1~N 层间移动,因此扳动到使升降梯移动到1 层以下、N 层以上的控制槽是不允许的。
电梯每移动一层,需要花费2 秒钟时间,而手柄从一个控制槽扳到相邻的槽,需要花费1 秒钟时间。探险队员现在在1 层,并且想尽快到达N 层,他们想知道从1 层到N 层至少需要多长时间?

输入格式

第一行两个正整数N、M。
第二行M 个整数C1、C2...CM。

输出格式

输出一个整数表示答案,即至少需要多长时间。若不可能到达输出-1。

样例输入

6 3
-1 0 2

样例输出

19

数据范围与约定

  • 对于30% 的数据,满足1≤N≤10,2<=M<=5。
    对于 100% 的数据,满足1≤N≤1000,2<=M<=20,-N<C1<C2<……<CM<N。

样例解释

手柄从第二个槽扳到第三个槽(0 扳到2),用时1 秒,电梯上升到3 层,用时4 秒。
手柄在第三个槽不动,电梯再上升到5 层,用时4 秒。
手柄扳动到第一个槽(2 扳到-1),用时2 秒,电梯下降到4 层,用时2 秒。
手柄扳动到第三个槽(-1 扳倒2),用时2 秒,电梯上升到6 层,用时4 秒。
总用时为(1+4)+4+(2+2)+(2+4)=19 秒。

来源

石家庄二中【Nescafé 28】杯NOIP模拟赛