问题描述:在一台超级计算机上,编号为1、2、...、n的n个作业等待批处理.批处理的任务就是将这n个作

业分成若于批,每批包含相邻的若干作业.从时刻0开始,分批加工这些作业.在每批作业开始前,机器需要启动时间S,而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和.单独完成第i个作业所需的时间是ti,所需的费用是它的完成时刻乘以一个费用系数fi.同批作业将在同一时刻完成.例如,如果在时刻T开始一批作业.则这批作业的完成时刻均为T+S+最优批处理问题就是要确定总费用最小的批处理方案.例如,假定有5个作业等待批处理,且

如果采用批处理方案{,2},{3},{4,5},则各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56),因此,这个批处理方案总费用是153.

算法设计:对于给定的待批处理的n个作业,计算其总费用最小的批处理方案.

数据输入:由文件input.txt提供输入数据.文件的第1行是待批处理的作业数n,第2行是启动时间S.接下来每行有2个数,分别为单独完成第i个作业所需的时间是1和所需的费用系数.

结果输出:将计算出的最小总费用输出到文件output.txt中.