logo AlgoBeat OnlineJudge
登录 注册

#10051. [蓝桥杯 2026 省 A] 外卖配送

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Dr_KC_Haus

题目描述

午高峰的外卖站点里,骑手小蓝正紧盯着屏幕上待处理的 个订单。这些订单必须严格按照系统列表中的固定顺序依次配送,不可打乱或跳过。为了顺利完成任务,小蓝计划将这 个订单分成若干个批次进行配送。

站点内停放着 种不同的交通工具,每种工具都具备两个属性:平均路途耗时 和箱体拥挤系数 。对于每一个批次,小蓝可以根据该批次订单的数量,从 种工具中独立选择一种最合适的。

假设某一个批次包含 个订单,且小蓝选用第 种交通工具,则该批次的总耗时由以下三部分组成:

  1. 路途耗时: 秒。
  2. 取餐耗时:由于箱内挤压,整理 个订单需处理 对挤压关系,每对耗时 ,共计 秒。
  3. 折返耗时:分批配送存在额外的折返成本。处理第一个批次时,由于小蓝默认已在站点装车完毕可以直接出发,此项耗时为 秒;但从第二个批次开始,每开启一个新的批次,都必须花费固定的 秒用于返回站点装载下一批订单。

现在,请你帮助小蓝规划最优的分批方案,并计算出送完 个订单所需的最小总耗时。

输入格式

一行包含三个整数 ,分别表示订单总数、交通工具的种类数,以及固定耗时。

接下来的 行,每行包含两个整数 ,依次表示第 种交通工具的平均路途耗时与箱体拥挤系数。

输出格式

输出一个整数,表示完成全部 个订单配送任务所需的最小总耗时(单位:秒)。

样例

输入输出样例 #1

输入 #1

5 2 40
10 8
2 20

输出 #1

118

数据范围与提示

【样例说明】

一种最优的方案是分成 批配送:

阶段 详情 耗时
批( 单,选工具 路途 ;取餐
折返 固定耗时
批( 单,选工具 路途 ;取餐
合计

【评测用例规模与约定】

对于 的评测用例,

对于所有评测用例,


本题目数据仅为民间数据。