P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps

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$ 秒。

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

### 数据范围 所有输入数据均满足以下条件： - $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 完成