Princess' Marriage

A tomboyish and brave princess of a poor country learned that gambling payouts are determined by the parimutuel system. Feeling she now understood gambling, she became certain of victory. As a result, she poured in more money than ever before and lost badly enough to squander all the taxes paid by the people. Taking this situation seriously, the king decided to marry the princess off to a neighboring country. He intended to make her reflect on her usual behavior, and at the same time to deepen ties with the neighboring country and receive financial aid.

The princess and the neighboring country's prince took a liking to each other, and the kings of both countries agreed to the political marriage. The princess set off for the neighboring country in high spirits with her meager money. Meanwhile, the prince's close aides in the neighboring country, who considered the princess's motive for marrying to be the king's one-sided pursuit of profit and were unhappy about it, sent countless assassins along the road to kill her.

The road the princess takes is already decided. Along the road she takes there are L lodgings in total. For convenience, the starting point and the destination are also lodgings, and each lodging is called S1, S2, ... SL. The princess starts at S1, visits the lodgings in ascending order (in the order S2, S3, ...), and finally goes to SL. At a lodging she can pay money to hire guards, and as long as she has money she can contract them for any distance she likes to protect her. The cost of hiring a guard is 1 gold per unit of distance. Note that the princess can also have only part of a segment she travels protected. The distance between Si and Si+1 is Di, and the expected number of times she is attacked by assassins per unit of distance between Si and Si+1 is given as Pi.

The princess has a budget M. Find the expected number of times she is attacked by assassins before reaching the destination when she hires guards so that this expected number is minimized.

The input consists of multiple data sets. Each data set has the following form.

N M
D1 P1
D2 P2
...
DN PN

The first line of each data set contains two integers: the number of segments N (1≤N≤10,000) and the budget M the princess has (0≤M≤1,000,000,000). The next N lines describe the road the princess takes. Each line contains two integers; the i-th line consists of the distance Di of the segment (1≤Di≤10,000) and the expected number of times she is attacked per unit of distance traveled through it, Pi (0≤Pi≤10). The end of the input is indicated by a data set with N=0, M=0. For this data set, no result may be output.

For each data set, output the expected number of times the princess is attacked by assassins before reaching the destination.