NC53260. 邮戳拉力赛
描述
题目译自 JOISC 2014 Day2 T3「スタンプラリー」
IOI铁路是由N+2个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为
。
这条路线上行驶的电车分为上行电车和下行电车两种，上行电车沿编号增大方向行驶，下行电车沿编号减小方向行驶。乘坐这两种电车的话，移动1站的距离需要T秒。换句话说，乘坐上行电车从车站i走到车站i+1需要T秒，乘坐下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车，或在N+1号车站乘坐上行电车。由于电车发车的频率非常高，你可以无视等待电车消耗的时间。
每个车站设有上行电车的站台和下行电车的站台，连接两个站台的道路上设有邮戳台。
现在，IOI铁路召开了邮戳拉力赛。在拉力赛中，选手需要从0号车站的上行电车站台出发，在
号车站各盖一枚邮戳，最终到达N+1号车站的上行电车站台即可完成。
为了在每个车站盖上邮戳，必须从电车上下来，步行走到车站通路上的邮戳台。在i号车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间如下所示：
这条路线上行驶的电车分为上行电车和下行电车两种，上行电车沿编号增大方向行驶，下行电车沿编号减小方向行驶。乘坐这两种电车的话，移动1站的距离需要T秒。换句话说，乘坐上行电车从车站i走到车站i+1需要T秒，乘坐下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车，或在N+1号车站乘坐上行电车。由于电车发车的频率非常高，你可以无视等待电车消耗的时间。
每个车站设有上行电车的站台和下行电车的站台，连接两个站台的道路上设有邮戳台。
现在，IOI铁路召开了邮戳拉力赛。在拉力赛中，选手需要从0号车站的上行电车站台出发，在
为了在每个车站盖上邮戳，必须从电车上下来，步行走到车站通路上的邮戳台。在i号车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间如下所示：
- 从车站i的上行电车站台到邮戳台的时间为
秒；
- 从车站i的邮戳台到上行电车站台的时间为
秒；
- 从车站i的下行电车站台到邮戳台的时间为
秒；
- 从车站i的邮戳台到下行电车站台的时间为
秒；
邮戳拉力赛的选手在0号车站与N+1号车站都只能停留一次。号车站都可以访问任意多次。
现在给出有邮戳台的车站个数、乘坐电车移动一站的时间、在每个车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间，请你求出完成邮戳拉力赛的最短时间。这个时间包括从0号车站出发，按下N个邮戳后到达N+1号车站的时间。无视等车的时间和按邮戳的时间。
输入描述
第一行两个空格分隔的整数N和T，表示有N+2个个车站，电车行驶一站的距离需要T秒。
接下来N行，第i行有四个空格分隔的整数，分别表示：
从车站i的上行电车站台到邮戳台的时间为从车站i的邮戳台到上行电车站台的时间为从车站i的下行电车站台到邮戳台的时间为从车站i的邮戳台到下行电车站台的时间为
输出描述
输出一行一个整数，表示完成邮戳拉力赛的最短时间。
示例1
输入:
4 1 1 1 1 1 1 9 9 1 9 9 1 1 1 9 9 1
输出:
23
说明:
从车站0出发，按照示例2
输入:
6 2 5 5 3 5 9 7 9 3 3 4 9 4 8 2 6 6 8 5 7 5 3 2 1 6
输出:
73