问题描述

太郎君在一个房间里有一个柜子、一个洗衣篮、一个垃圾箱、一家服装店和一个自助洗衣店。初始时，柜子、洗衣篮和垃圾箱都是空的，太郎君没有任何衬衫。

太郎君每天早上可以在房间里的服装店买衬衫。这家服装店有 $N$ 种类型的衬衫，每种类型有 $10^{100}$ 件。第 $i$ 种类型的衬衫洗 $A_i$ 次后就会破掉，价格为 $B_i$ 元。购买的衬衫会立即放入柜子。

太郎君每天的生活方式如下：

• 早上：可以在服装店购买任意数量、任意种类的衬衫。
• 中午：从柜子中选择一件衬衫穿上，然后将穿过的衬衫放入洗衣篮。
• 晚上：选择是否洗衣服。
  • 如果选择洗衣服：支付 $C$ 元使用自助洗衣店，将洗衣篮中的所有衬衫洗净。然后将破掉的衬衫放入垃圾箱，将其他衬衫放回柜子。
  • 如果选择不洗衣服：什么都不发生。

给定当前是第 $1$ 天早上，求太郎君在第 $M$ 天晚上之前每天穿衬衫所需的最小资金量。

约束条件

• $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$ 都是整数

输入

输入以以下格式从标准输入中给出。

$N$ $M$ $C$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出

输出答案，占一行。

输入示例 1

2 3 1
1 2
2 3

输出示例 1

6

以下是最佳操作步骤，此时需要的资金总额为 $6$ 元。

• 第 $1$ 天
  • 早上：购买第 $1$ 类型的衬衫 $1$ 件，将其记为衬衫 $a$。
  • 中午：穿上柜子里的衬衫 $a$，然后将穿过的衬衫放入洗衣篮。
  • 晚上：选择不洗衣服。
• 第 $2$ 天
  • 早上：购买第 $2$ 类型的衬衫 $1$ 件，将其记为衬衫 $b$。
  • 中午：穿上柜子里的衬衫 $b$，然后将穿过的衬衫放入洗衣篮。
  • 晚上：选择洗衣服。由于衬衫 $a$ 破了，将其放入垃圾箱；衬衫 $b$ 放回柜子。
• 第 $3$ 天
  • 早上：不购买任何衬衫。
  • 中午：穿上柜子里的衬衫 $b$，然后将穿过的衬衫放入洗衣篮。
  • 晚上：选择不洗衣服。

输入示例 2

15 551 34
7 78
24 9
7 20
23 17
22 64
3 37
5 18
14 11
1 16
23 43
19 51
2 4
14 11
23 44
21 78

输出示例 2

788

输入示例 3

1 1000000000 1000000000
1 1000000000

输出示例 3

1000000000000000000