AT_ddcc_2016_final_d シャツの部屋

太郎君在一个房间里，房间里有衣柜、洗衣篮、垃圾桶、服装店和投币洗衣店。最初，衣柜、洗衣篮和垃圾桶都是空的，太郎君也没有任何衬衫。 太郎君每天早上可以在房间里的服装店购买衬衫。服装店里有 $N$ 种衬衫，每种衬衫都有 $10^{100}$ 件。第 $i$ 种衬衫穿 $A_i$ 次洗涤后会破损，价格为 $B_i$ 日元。购买的衬衫会立刻放入衣柜。 太郎君每天的生活如下： - 早上：可以在服装店购买衬衫，种类和数量不限。 - 中午：从衣柜中选择 $1$ 件衬衫穿上，然后将穿过的衬衫放入洗衣篮。 - 晚上：选择是否洗衣。 - 如果洗衣：支付 $C$ 日元使用投币洗衣店，将洗衣篮中的所有衬衫洗净。洗涤后破损的衬衫会被扔进垃圾桶，其余的衬衫放回衣柜。 - 如果不洗衣：什么都不做。 现在从第 $1$ 天的早上开始，到第 $M$ 天的晚上结束，请你求出太郎君每天都能穿上衬衫所需的最小资金。

输入按以下格式从标准输入读入。 > $N$ $M$ $C$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_N$ $B_N$

请输出一个整数，表示所需的最小资金。

## 限制条件 - $1 \leq N \leq 500$ - $1 \leq M \leq 10^{9}$ - $1 \leq A_i \leq 500$ - $1 \leq B_i \leq 10^{9}$ - $1 \leq C \leq 10^{9}$ - $B_i$ 和 $C$ 均为整数 ## 样例解释 1 最优的做法如下，总共需要 $6$ 日元。 - 第 $1$ 天 - 早上：购买 $1$ 件第 $1$ 种衬衫，记为衬衫 $a$。 - 中午：穿上衣柜中的衬衫 $a$，然后放入洗衣篮。 - 晚上：选择不洗衣。 - 第 $2$ 天 - 早上：购买 $1$ 件第 $2$ 种衬衫，记为衬衫 $b$。 - 中午：穿上衣柜中的衬衫 $b$，然后放入洗衣篮。 - 晚上：洗衣。衬衫 $a$ 因洗涤而破损被扔进垃圾桶，衬衫 $b$ 放回衣柜。 - 第 $3$ 天 - 早上：什么都不买。 - 中午：穿上衣柜中的衬衫 $b$，然后放入洗衣篮。 - 晚上：选择不洗衣。 由 ChatGPT 4.1 翻译