Problem Description

Taro is in a room with a wardrobe, a laundry basket, a trash can, a clothing store, and a coin laundry. Initially, the wardrobe, laundry basket, and trash can are empty, and Taro has no shirts.

Every morning, Taro can buy shirts at the clothing store in the room. There are $ N $ types of shirts available at the store, each with $ 10^{100} $ pieces. The shirts of type $ i $ will tear after $ A_i $ washes and cost $ B_i $ yen. The purchased shirts are immediately stored in the wardrobe.

Taro lives his daily life as follows:

• Morning: He can buy shirts at the clothing store. He can buy any number of types and pieces.
• Noon: He chooses one shirt from the wardrobe to wear. Then, he puts the worn shirt in the laundry basket.
• Evening: He chooses whether to do laundry or not.
• If he does laundry: He pays $ C $ yen to use the coin laundry to wash all the shirts in the laundry basket. Then, he puts the torn shirts in the trash can and the rest back in the wardrobe.
• If he does not do laundry: Nothing happens.

Starting from the morning of day 1, find the minimum amount of money Taro needs to wear a shirt every day until the evening of day $ M $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

2 3 1
1 2
2 3

Sample Output #1

6

Sample Input #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

Sample Output #2

788

Sample Input #3

1 1000000000 1000000000
1 1000000000

Sample Output #3

1000000000000000000

Notes/Hints

Constraints

• $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}$
• Both $ B_i $ and $ C $ are integers.

Sample Explanation 1

The optimal actions are as follows, requiring a total of $ 6 $ yen:
- Day 1
- Morning: Buy 1 piece of type 1 shirt, referred to as shirt $ a $.
- Noon: Wear shirt $ a $ and put it in the laundry basket.
- Evening: Choose not to do laundry.
- Day 2
- Morning: Buy 1 piece of type 2 shirt, referred to as shirt $ b $.
- Noon: Wear shirt $ b $ and put it in the laundry basket.
- Evening: Do laundry. Shirt $ a $ tears and goes to the trash can, shirt $ b $ is put back in the wardrobe.
- Day 3
- Morning: Buy nothing.
- Noon: Wear shirt $ b $ and put it in the laundry basket.
- Evening: Choose not to do laundry.

见题面 Input 部分

见题面 Output 部分