Problem: Hearing that energy drinks increase rating in those sites, Takahashi decides to buy up M cans of energy drinks.

There are N stores that sell energy drinks. In the i-th store, he can buy at most B_i cans of energy drinks for A_i yen (the currency of Japan) each.

What is the minimum amount of money with which he can buy M cans of energy drinks?

It is guaranteed that, in the given inputs, a sufficient amount of money can always buy M cans of energy drinks.

Constraints

* All values in input are integers.
* 1 \leq N, M \leq 10^5
* 1 \leq A_i \leq 10^9
* 1 \leq B_i \leq 10^5
* B_1 + ... + B_N \geq M

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N


Output

Print the minimum amount of money with which Takahashi can buy M cans of energy drinks.

Examples

Input

2 5
4 9
2 4


Output

12


Input

4 30
6 18
2 5
3 10
7 9


Output

130


Input

1 100000
1000000000 100000


Output

100000000000000

Solution (in JAVA):

Solution:
import java.util.Scanner;

import java.util.*;
import static java.util.Comparator.*;

public class Main{
	static class V{
		long a;
		long b;
		long a(){
			return a;
		}
		long b(){
			return b;
		}
		V(long a, long b){
			this.a = a;
			this.b = b;
		}
	}
	
	static public void  main(String[] args){
		Scanner scan = new Scanner(System.in);

		int n  = scan.nextInt();
		long m  = scan.nextLong();

		List<V> a = new ArrayList<V>(n);


		for (int i = 0; i < n; i++){
			a.add(new V(scan.nextLong(),scan.nextLong()));
		}

		a.sort(comparing(V::a));
		Iterator<V> it = 		a.iterator();

		long cur = 0;
		long sum = 0;
		while(it.hasNext()){
			V v = it.next();
			//			System.err.println(v.a());
			if(cur + v.b() < m) {
				cur += v.b();
				sum += v.b() * v.a();
			}else{
				sum += (m - cur) * v.a();
				System.out.println(sum);
				return;
			}
		}

	}

}