IUBAT Fruit Fest
Author: Efat Sikder
Problem Setter: Nazmul kabir TusharAlumni, IUBAT IITS Programming Club
IUBAT is organizing its inaugural Fruit Festival, and your friends are enthusiastic participants with a fruit shop offering a variety of fruits. Their shop features N different types of fruits, each with its own price and available quantity.
You want to assist your friends in preparing for the festival while being mindful of your budget for an upcoming programming contest. Your objective is to purchase the maximum number of fruits possible at the lowest overall cost.
Currently, you are at the library, and dealing with a multitude of fruit options manually would be time-consuming. As a result, you've decided to create a computer program to streamline this task.
Input Format
⮞ The first line of the input will specify N (1 ≤ N ≤ 103), representing the number of fruit varieties your friends are selling.
⮞ The second line will specify C (1 ≤ C ≤ 104), indicating the maximum quantity of fruits that can fit in your basket.
⮞ The following N lines will each contain two integers, Pi (1 ≤ Pi ≤ 1000) and Qi (1 ≤ Qi ≤ 1000), denoting the price and quantity of the ith fruit type.
Output Format
⦿ You should output the minimum amount of money you need to spend to acquire fruits optimally for the festival.
Print a new line after printing the output.
Samples
Input
Output
Language | Time | Memory |
GNU C 11 | 1s | 32MB |
GNU C++ 14 | 1s | 32MB |
GNU C++ 11 | 1s | 32MB |