题目描述

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$，从上行电车站台到打卡点需要 $U_i$ 秒，从打卡点返回上行电车站台需要 $V_i$ 秒；从下行电车站台到打卡点需要 $D_i$ 秒，从打卡点返回下行电车站台需要 $E_i$ 秒。

需要注意的是，打卡活动的参与者只能各访问车站 $0$ 和车站 $N+1$ 一次，而车站 $1$ 到车站 $N$ 可以任意多次下车。

题目

给定打卡车站的数量、电车移动一个车站所需的时间、各车站的上行电车站台与打卡点之间的移动时间、以及各车站的下行电车站台与打卡点之间的移动时间，编写一个程序，求出完成打卡活动所需的最短时间。

完成打卡活动所需的时间是指：从车站 $0$ 出发，依次打卡 $N$ 个车站，最终到达车站 $N+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$ 秒。

输出格式

在标准输出中，输出一行，表示完成打卡活动所需的最短时间（以秒为单位的整数）。

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

23

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

提示

数据范围

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

• $1 \le N \le 3000$
• $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 分]

无额外限制。

翻译由 Qwen3-235B 完成