501. Maximum Unit of Boxes

0

Easy

You have been assigned the task of loading a certain number of boxes onto a single truck. You are given a 2D array called boxTypes, where each element boxTypes[i] = [numberOfBoxes(i), numberOfUnitsPerBox(i)] represents a type of box: * numberOfBoxes(i) is the number of boxes of type i. * numberOfUnitsPerBox(i) is the number of units contained in each box of type i.

You are also given an integer called truckSize, which represents the maximum number of boxes that can be loaded onto the truck. You can choose any boxes to load onto the truck as long as the total number of boxes does not exceed truckSize. Your task is to determine the maximum total number of units that can be loaded onto the truck.

Input Format

The first line contains two space-separated integers N and K, representing the number of box types and the truck size, respectively.
The next N lines contain the box types, where each box type is represented by two integers.

Output Format

An integer representing the maximum number of units that can be loaded onto the truck.

Example

Input

4 10 5 10 2 5 4 7 3 9

Output

91

Constraints

1 <= boxTypes.length <= 1000
1 <= numberOfBoxes(i), numberOfUnitsPerBox(i) <= 1000
1 <= truckSize <= 106