#P5614. 「一本通 5.6 例 1」任务安排 1
「一本通 5.6 例 1」任务安排 1
「一本通 5.6 例 1」任务安排 1
题目描述
一台机器要按编号顺序处理 个任务。从时刻 开始,机器依次处理若干批任务,每批包含连续的一个或多个任务。
每批都需要启动时间 。若一批包含任务 ,并在时刻 开始,则这批任务都在时刻 完成。下一批从这个时刻开始处理。
任务 的费用等于其完成时刻乘以费用系数 。求所有任务的最小总费用。
输入格式
第一行一个整数 。第二行一个整数 。
接下来 行,第 行有两个正整数 ,分别表示任务 的处理时间与费用系数。
输出格式
输出一行一个整数,表示最小总费用。
样例 1
5
1
1 3
3 2
4 3
2 3
1 4
153
一个最优方案将任务分为三批 、、,五个任务的完成时刻依次为 ,总费用为 。
数据范围
,,。
相关
在下列比赛中: