{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"有一台机器需要处理一个包含N个作业的序列。作业编号从1到N,因此序列是1,2,...,N。作业序列必须被划分为一个或多个批次,其中每个批次由序列中连续的作业组成。处理从时间0开始。批次将依次处理,从第一批开始。如果批次b包含比批次c编号小的作业,则批次b在批次c之前处理。批次中的作业将在机器上依次处理。在批次中的所有作业处理完毕后,机器将输出该批次中所有作业的结果。作业j的输出时间是包含j的批次完成的时间。\r\u003cbr\u003e\r\u003cbr\u003e每个批次需要设置时间S来准备机器。对于每个作业i,我们知道其成本因子Fi和处理所需时间Ti。如果一个批次包含作业x, x+1,... , x+k,并且在时间t开始,则该批次中每个作业的输出时间为t + S + (T\u003csub\u003ex\u003c/sub\u003e + T\u003csub\u003ex+1\u003c/sub\u003e + ... + T\u003csub\u003ex+k\u003c/sub\u003e)。注意,机器同时输出批次中所有作业的结果。如果作业i的输出时间是Oi,其成本为Oi * Fi。例如,假设有5个作业,设置时间S \u003d 1,(T1, T2, T3, T4, T5) \u003d (1, 3, 4, 2, 1),以及(F1, F2, F3, F4, F5) \u003d (3, 2, 3, 3, 4)。如果作业被划分为三个批次{1, 2},{3},{4, 5},则输出时间(O1, O2, O3, O4, O5) \u003d (5, 5, 10, 14, 14),作业的成本分别为(15, 10, 30, 42, 56)。上述划分的总成本为153。\r\u003cbr\u003e\r\u003cbr\u003e你需要编写一个程序,给定批次设置时间和作业序列及其处理时间和成本因子,计算可能的最小总成本。\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"你的程序从标准输入中读取。第一行包含作业数量N,1 \u0026lt;\u003d N \u0026lt;\u003d 10000。第二行包含批次设置时间S,为整数,0 \u0026lt;\u003d S \u0026lt;\u003d 50。接下来的N行包含关于作业1, 2,..., N的信息,顺序如下。每行首先是一个整数Ti,1 \u0026lt;\u003d Ti \u0026lt;\u003d 100,作业的处理时间。然后是一个整数Fi,1 \u0026lt;\u003d Fi \u0026lt;\u003d 100,作业的成本因子。"}},{"title":"输出","value":{"format":"HTML","content":"你的程序将写入标准输出。输出包含一行,其中包含一个整数:可能的最小总成本。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n1\r\n1 3\r\n3 2\r\n4 3\r\n2 3\r\n1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e153\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}