#P2365. 任务安排
任务安排
题目描述
个任务排成一个序列在一台机器上等待完成(顺序不得改变),这 个任务被分成若干批,每批包含相邻的若干任务。
从零时刻开始,这些任务被分批加工,第 个任务单独完成所需的时间为 。在每批任务开始前,机器需要启动时间 ,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。
每个任务的费用是它的完成时刻乘以一个费用系数 。请确定一个分组方案,使得总费用最小。
输入格式
第一行一个正整数 。
第二行是一个整数 。
下面 行每行有一对数,分别为 和 ,表示第 个任务单独完成所需的时间是 及其费用系数 。
输出格式
一个数,最小的总费用。
5
1
1 3
3 2
4 3
2 3
1 4
153
提示
【数据范围】
对于 的数据,,,。
【样例解释】
如果分组方案是 ,则完成时间分别为 ,费用 ,总费用就是 。