#1740. [Usaco2005 mar]Yogurt factory 奶酪工厂

[Usaco2005 mar]Yogurt factory 奶酪工厂

题目描述

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next n (1n104)n \ (1 \le n \le 10^4) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company ci (1ci5×103)c_i \ (1 \le c_i \le 5\times 10^3) cents to produce one unit of yogurt in week ii. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week. Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of s (1s100)s \ (1 \le s \le 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt. Yucky wants to find a way to make weekly deliveries of yi (0yi104)y_i \ (0 \le y_i \le 10^4) units of yogurt to its clientele (yiy_i is the delivery quantity in week ii). Help Yucky minimize its costs over the entire Nweek period. Yogurt produced in week ii, as well as any yogurt already in storage, can be used to meet Yucky's demand for that week.

牛们收购了一个奶酪工厂,接下来的 nn 个星期里,牛奶价格和劳力价格不断起伏。第 ii 周,生产一个单位奶酪需要 cic_i 便士。工厂有一个货栈,保存一单位奶酪,每周需要 ss 便士,这个费用不会变化。货栈十分强大,可以存无限量的奶酪,而且保证它们不变质。工厂接到订单,在第 ii 周需要交付 yiy_i 单位的奶酪给委托人。第 ii 周刚生产的奶酪,以及之前的存货,都可以作为产品交付。请帮牛们计算这段时间里完成任务的最小代价。

输入格式

  • Line 11: Two space-separated integers, nn and ss.
  • Lines 2n+12\dots n+1: Line i+1i+1 contains two space-separated integers: cic_i and yiy_i.
  • 第一行输入两个整数 nnss
  • 接下来 nn 行输入 cic_iyiy_i

输出格式

  • Line 11: Line 11 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32-bit integer.
  • 输出最少的代价。注意,可能超过 32 位长整型。
4 5
88 200
89 400
97 300
91 500
126900

样例说明

11 周生产 200200 单位奶酪并全部交付;第 22 周生产 700700 单位,交付 400400 单位,有 300300 单位;第 33 周交付 300300 单位存货;第 44 周生产并交付 500500 单位。

数据规模与约定

对于 100%100\% 的数据,1n1041\le n\le 10^41ci5×1031 \leq c_i \leq 5\times 10^31s1001 \leq s \leq 1000yi1040 \leq y_i \leq 10^4

题目来源

Gold