题目描述
有N 个作业要在一台机器上处理，编号为1～N 。作业序列不得改变，可以划分为一个或多个批次，其中每个批次都由序列中的连续作业组成。处理从时间0和第1批作业开始，一批一批地处理。批次中的作业在机器上依次处理，处理完一个批次中的所有作业后，机器立即输出该批次中所有作业的结果。作业j 的输出时间是包含j 的批处理完成的时间。
在每个批次启动机器都需要S 时间。对每个作业i ，其处理时间都为Ti ，费用系数都为Fi 。若批处理包含作业x , x +1, …, x +k，从时间t 开始，则该批次中每个作业的输出时间都为t +S +(Tx +Tx+1 +…+Tx + k )。若作业i 的输出时间为Oi ，则其成本为Oi ×Fi 。
假设有5个作业，启动时间S =1，(T1 , T2 , T3 , T4 , T5)=(1, 3, 4, 2, 1)，(F1 , F2 , F3 , F4 , F5 )=(3, 2, 3, 3,4)。若将作业分成三批{1, 2}、{3}、{4, 5}，则输出时间为(5, 5,10, 14, 14)，成本为(15, 10, 30, 42, 56)，总成本是所有作业成本的总和153。
输入
第1行包含作业数N （1≤N ≤10000），第2行包含批次启动时间整数S （0≤S ≤50）。以下N 行，每行都包含两个整数，即作业的处理时间Ti 和费用系数Fi （1≤Ti ，Fi ≤100）。