Description

IOI 铁路是由 N+2 个站点构成的直线线路. 这条线路的车站从某一端的车站开始顺次标号为 \(0, 1, 2, \ldots, n+1\).

这条路线上行驶的电车分为上行电车和下行电车两种, 上行电车沿编号增大方向行驶, 下行 电车沿编号减小方向行驶. 乘坐这两种电车的话, 移动 \(1\) 站的距离需要 \(t\) 秒. 换句话说, 乘坐上行电车从车站 \(i\) 走到车站 \(i+1\) 需要 \(t\) 秒, 乘坐下行电车从车站 \(i\) 走到车站 \(i-1\) 也需要 \(t\) 秒. 你不能在 \(0\) 号车站乘坐下行电车, 或在 \(n+1\) 号车站乘坐上行电车. 由于电车发车的频率非常高, 你可以无视等待电车消耗的时间.

每个车站设有上行电车的站台和下行电车的站台, 连接两个站台的道路上设有邮戳台.

现在, IOI 铁路召开了邮戳拉力赛. 在拉力赛中, 选手需要从 \(0\) 号车站的上行电车站台 出发, 在 \(1, 2, \ldots, n\) 号车站各盖一枚邮戳, 最终到达 \(n+1\) 号车站的上行电车 站台即可完成.

为了在每个车站盖上邮戳, 必须从电车上下来, 步行走到车站通路上的邮戳台. 在 \(i\) 号车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间如下所示:

  • 从车站 \(i\) 的上行电车站台到邮戳台的时间为 \(U_i\) 秒
  • 从车站 \(i\) 的邮戳台到上行电车站台的时间为 \(V_i\) 秒
  • 从车站 \(i\) 的下行电车站台到邮戳台的时间为 \(D_i\) 秒
  • 从车站 \(i\) 的邮戳台到下行电车站台的时间为 \(E_i\) 秒

邮戳拉力赛的选手只能访问 \(0\) 号车站与 \(n+1\) 号车站各一次.\(1, 2, \ldots, n\) 号车站都可以访问任意多次.

现在给出有邮戳台的车站个数、乘坐电车移动一站的时间、在每个车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间, 请你求出完成邮戳拉力赛的最短时间.

这个时间包括从 \(0\) 号车站出发, 按下 \(n\) 个邮戳后到达 \(n+1\) 号车站的时间. 无视 等车的时间和按邮戳的时间.

Input

第一行两个空格分隔的整数 \(n, t\), 表示有 \(n+2\) 个车站, 电车行驶一站的距离需要 \(t\) 秒;

接下来 \(n\) 行, 第 \(i\) 行有四个空格分隔的整数 \(U_i, V_i, D_i, E_i\), 分别表示题干中表示的含义.

Output

输出一行一个整数, 表示完成邮戳拉力赛的最短时间.

Sample Input

4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1

Sample Output

23

Data Range

对于所有数据, 满足:\(1 \leq n \leq 3000, 1 \leq t \leq 10^5, 1 \leq U_i, V_i, D_i, E_i \leq 10^5\)

Explanation

一道很奇怪的背包问题......

因为所有人都要从左边走到右边对吧...... 而且反反复复走很多遍一点意义都没有对吧...... 所以只会出现几个往回走的环, 而且环一般不会交叉 (逃).

然后只要统计这些环出现的次数与当前的位置的关系就可以了.

然后 \(dp[i][j]\) 表示在第 \(i\) 个位置, 从上行站台走到下行站台比 (反之) 多的次数为 \(j\) 的最短时间.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
#define minimize(__x,__y) __x=min(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 3010;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n, t;
lli dp[maxn][maxn];
int u[maxn], v[maxn], d[maxn], e[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d%d", &u[i], &v[i], &d[i], &e[i]);
    // Setting large limits
    rep(i, 0, n+1) rep(j, 0, n+1)
        dp[i][j] = infinit;
    // Knapsack problem
    dp[0][0] = 0;
    rep(i, 1, n) {
        range(0,n) dp[i-1][_] += _*t*2;
        #define update(__x) minimize(dp[i][j],__x);
        rep(j,0,n-1) update(dp[i-1][j+1] + u[i] + e[i]);
        rep(j,1,n) update(dp[i-1][j-1] + d[i] + v[i]);
        rep(j,0,n) update(dp[i-1][j] + u[i] + v[i]);
        rep(j,1,n) update(dp[i-1][j] + d[i] + e[i]);
        rep(j,0,n-1) update(dp[i][j+1] + u[i] + e[i]);
        rep(j,1,n) update(dp[i][j-1] + d[i] + v[i]);
    }
    lli res = dp[n][0] + t*(n+1);
    printf("%lld\n", res);
    return 0;
}