Crystal Ball Factory

The Astrologically Clairvoyant Manufacturers (ACM),a pioneer in future-predicting technology, just landed a contract to manufacture crystal balls for weather forecasters around the world. Every week, a variable number of crystal balls needs to be delivered; the required amount for each week is specified in the contract.



Crystal balls are made from the highest-quality crystal, whose price fluctuates from week to week. Fortunately, the ACM is able to foresee the price of crystal for the coming weeks, thanks to its own future-predicting technology.

When the price is low, the ACM would like to buy crystal and manufacture crystal balls, storing any excess in their warehouse. On the other hand, in weeks for which the price is high, ACM would rather use the crystal balls stored in the warehouse to satisfy the demand specified in their contract. However, since there is a also a fixed weekly cost to store each crystal ball in the warehouse, and an initial cost for turning on the manufacturing machines and producing a non-zero quantity of crystal balls, the decision is not always simple.

Can you help them fulfill their contract at minimal cost?

The first line of each test case (representing a contract) will contain the number of weeks for which the contract will last.

The next line will contain the non-negative integers b, k and n, where b is the base cost for manufacturing a non-zero quantity of crystal balls on a given week, k is the cost for storing each crystal ball in the warehouse for a week, and n is the maximum capacity of the warehouse.

The following lines will describe the weeks specified in the contract in chronological order. Each week is described by a single line which will contain a pair of non-negative integers c and r, where c is the cost for manufacturing a new crystal ball using new crystal bought this week, and r is the number of crystal balls which must be delivered this week. A crystal ball can be manufactured and delivered in the same week if appropriate, in which case it won’t need to be stored in the warehouse at all.

The last line of the input will contain the integer 0 and should not be processed.

For each test case, output the minimum amount which the ACM will have to spend in order to fulfill the entire contract. All the numbers in the input will be at most 1000.

4
1 0 1000
1 1
12 4
1 0
1000 1000
2
0 100 1
1 1000
1000 101
0

1007
101101

IPCP 2005 Northern Preliminary for Northeast North-America