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

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next weeks, the price of milk and labor will fluctuate weekly such that it will cost the company cents to produce one unit of yogurt in week . 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 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 units of yogurt to its clientele ( is the delivery quantity in week ). Help Yucky minimize its costs over the entire Nweek period. Yogurt produced in week , as well as any yogurt already in storage, can be used to meet Yucky's demand for that week.

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

• Line : Two space-separated integers, and .
• Lines : Line contains two space-separated integers: and .
• 第一行输入两个整数 和 。
• 接下来 行输入 和 。

• Line : Line 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 位长整型。

样例输入 #1

4 5
88 200
89 400
97 300
91 500

样例输出 #1

126900

样例说明

第 周生产 单位奶酪并全部交付；第 周生产 单位，交付 单位，有 单位；第 周交付 单位存货；第 周生产并交付 单位。

对于 的数据，，，，。 Gold