在一台机器上有一系列N个作业要处理。作业的编号从1到N，因此序列为1,2，...，N。作业序列必须分为一个或多个批次，其中每个批次由序列中的连续作业组成。处理从时间0开始。批次从第一批开始逐个处理，如下所述。如果批次b包含编号小于批次c的作业，则批次b在批次c之前处理。批处理中的作业在机器上连续处理。处理完批次中的所有作业后，机器立即输出该批次中所有作业的结果。作业j的输出时间是包含j的批处理完成的时间。
设置每个批次的机器需要设置时间S.对于每个工作i，我们知道其成本因子Fi和处理它所需的时间Ti。如果批处理包含作业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}，那么输出时间（O1，O2，O3，O4，O5）=（5,5,10,14,14）这些工作的成本分别为（15,10,30,42,56）。分区的总成本是所有作业的成本之和。上面的示例分区的总成本是153。
您将编写一个程序，根据批处理设置时间和一系列作业及其处理时间和成本因素，计算最小可能的总成本。
5
1
1 3
3 2
4 3
2 3
1 4153