IOI 铁道有一条直线线路，由 $N+2$ 个车站组成。这些车站从线路的一端开始，依次编号为 $0$ 到 $N+1$。

该线路上运行着上行电车和下行电车两种电车。乘坐上行电车可以向车站编号增大的方向移动，乘坐下行电车可以向车站编号减小的方向移动。乘坐这些电车移动一个车站需要 $T$ 秒。也就是说，乘坐上行电车时，从车站 $i$ 到车站 $i+1$ 需要 $T$ 秒；乘坐下行电车时，从车站 $i$ 到车站 $i-1$ 需要 $T$ 秒。但是，不能从车站 $N+1$ 乘坐上行电车，也不能从车站 $0$ 乘坐下行电车。电车发车频率极高，等待电车的时间可以忽略不计。

每个车站都有上行电车站台和下行电车站台。连接这两个站台的通道中间设有盖章台。

目前，IOI 铁道正在举办集章拉力赛。参加者从车站 $0$ 的上行电车站台出发，依次盖下车站 $1$ 到车站 $N$ 的印章，最后到达车站 $N+1$ 的上行电车站台即视为完成。

为了在各车站盖章，必须从电车下车，步行至车站通道中间的盖章台。在车站 $i$ 的上行电车站台、盖章台以及下行电车站台之间移动所需的时间分别为：

• 从车站 $i$ 的上行电车站台到盖章台：$U_i$ 秒
• 从盖章台到车站 $i$ 的上行电车站台：$V_i$ 秒
• 从车站 $i$ 的下行电车站台到盖章台：$D_i$ 秒
• 从盖章台到车站 $i$ 的下行电车站台：$E_i$ 秒

但是，集章拉力赛的参加者只能访问车站 $0$ 和车站 $N+1$ 各一次。对于车站 $1$ 到车站 $N$，可以多次下车。

车站 $i$ 的结构

题目描述

给定盖章车站的数量、乘坐电车移动一个车站所需的时间，以及各车站上行电车站台与盖章台之间、下行电车站台与盖章台之间的移动时间。请编写一个程序，求出完成集章拉力赛所需的最短时间。

完成集章拉力赛所需的时间，是指从车站 $0$ 出发，盖下 $N$ 个印章，并到达车站 $N+1$ 的上行电车站台所花费的时间。注意，在站台等待电车的时间以及盖章所需的时间可以忽略不计。

输入格式

从标准输入读取以下数据：

• 第 $1$ 行包含两个整数 $N, T$，以空格分隔。这表示车站总数为 $N+2$ 个，乘坐电车移动一个车站需要 $T$ 秒。
• 接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 包含四个整数 $U_i, V_i, D_i, E_i$，以空格分隔。这表示：
  • 从车站 $i$ 的上行电车站台到盖章台需 $U_i$ 秒
  • 从盖章台到车站 $i$ 的上行电车站台需 $V_i$ 秒
  • 从车站 $i$ 的下行电车站台到盖章台需 $D_i$ 秒
  • 从盖章台到车站 $i$ 的下行电车站台需 $E_i$ 秒

输出格式

将完成集章拉力赛所需的最短时间（以秒为单位）作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 3\,000$
• $1 \le T \le 100\,000$
• $1 \le U_i \le 100\,000$ ($1 \le i \le N$)
• $1 \le V_i \le 100\,000$ ($1 \le i \le N$)
• $1 \le D_i \le 100\,000$ ($1 \le i \le N$)
• $1 \le E_i \le 100\,000$ ($1 \le i \le N$)

子任务

子任务 1 [10 分] * 满足 $N \le 16$。

子任务 2 [75 分] * 满足 $N \le 100$。

子任务 3 [15 分] * 无附加限制。

样例

样例输入 1

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

样例输出 1

23

说明 1

从车站 $0$ 出发，按车站 $2, 1, 4, 3, 1, 5$ 的顺序访问，可以以最短时间完成集章拉力赛。

样例输入 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

样例输出 2

73