题目描述

奶牛们购买了一家生产世界著名的“难吃酸奶”的酸奶工厂。在接下来的 $N (1 <= N <= 10,000)$ 周里，由于牛奶和劳动力成本的每周波动，生产一单位酸奶将花费公司 $C_i (1 <= C_i <= 5,000)$ 美分。难吃酸奶工厂设计良好，每周可以生产任意多的酸奶。

难吃酸奶拥有一个仓库，可以以每单位酸奶每周 $S (1 <= S <= 100)$ 美分的恒定费用存储未使用的酸奶。幸运的是，酸奶不会变质。难吃酸奶的仓库非常大，可以存放任意多的酸奶。

难吃酸奶希望找到一种方法，在整个 $N$ 周期间，以最小的成本进行每周 $Y_i (0 <= Y_i <= 10,000)$ 单位酸奶的交付 ($Y_i$ 是第 $i$ 周的交付量)。请帮助难吃酸奶将总成本降到最低。第 $i$ 周生产的酸奶以及任何已经存储的酸奶可以用来满足该周的需求。

输入格式

• 第 1 行：两个空格分隔的整数 $N$ 和 $S$。
• 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含两个空格分隔的整数：$C_i$ 和 $Y_i$。

输出格式

第 1 行：一个整数，表示满足酸奶交付计划的最小总成本。

4 5
88 200
89 400
97 300
91 500

126900

数据规模与约定