P16229 [蓝桥杯 2026 省 A] 外卖配送

午高峰的外卖站点里，骑手小蓝正紧盯着屏幕上待处理的 $N$ 个订单。这些订单必须严格按照系统列表中的固定顺序依次配送，不可打乱或跳过。为了顺利完成任务，小蓝计划将这 $N$ 个订单分成若干个批次进行配送。 站点内停放着 $M$ 种不同的交通工具，每种工具都具备两个属性：平均路途耗时 $A_i$ 和箱体拥挤系数 $B_i$。对于每一个批次，小蓝可以根据该批次订单的数量，从 $M$ 种工具中独立选择一种最合适的。 假设某一个批次包含 $L$ 个订单，且小蓝选用第 $i$ 种交通工具，则该批次的总耗时由以下三部分组成： 1. 路途耗时：$L \times A_i$ 秒。 2. 取餐耗时：由于箱内挤压，整理 $L$ 个订单需处理 $\frac{L(L-1)}{2}$ 对挤压关系，每对耗时 $B_i$，共计 $\frac{L(L-1)}{2} \times B_i$ 秒。 3. 折返耗时：分批配送存在额外的折返成本。处理第一个批次时，由于小蓝默认已在站点装车完毕可以直接出发，此项耗时为 $0$ 秒；但从第二个批次开始，每开启一个新的批次，都必须花费固定的 $X$ 秒用于返回站点装载下一批订单。 现在，请你帮助小蓝规划最优的分批方案，并计算出送完 $N$ 个订单所需的最小总耗时。

一行包含三个整数 $N$、$M$ 和 $X$，分别表示订单总数、交通工具的种类数，以及固定耗时。 接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，依次表示第 $i$ 种交通工具的平均路途耗时与箱体拥挤系数。

输出一个整数，表示完成全部 $N$ 个订单配送任务所需的最小总耗时（单位：秒）。

### 【样例说明】 一种最优的方案是分成 $2$ 批配送： | 阶段 | 详情 | 耗时 | |:--|:--|:--| | 第 $1$ 批（$2$ 单，选工具 $2$） | 路途 $2 \times 2 = 4$；取餐 $\frac{2 \times 1}{2} \times 20 = 20$ | $24$ 秒 | | 折返 | 固定耗时 | $40$ 秒 | | 第 $2$ 批（$3$ 单，选工具 $1$） | 路途 $3 \times 10 = 30$；取餐 $\frac{3 \times 2}{2} \times 8 = 24$ | $54$ 秒 | | 合计 | < | $\mathbf{118}$ **秒** | ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$1 \le N, M \le 100$； 对于所有评测用例，$1 \le N, M \le 5000$，$1 \le X, A_i, B_i \le 10^9$。