409488: GYM103584 A New Garden

Phoenix is redecorating his massive backyard and decides that he has space for $$$m$$$ total trees and he would like to maximize the beauty of his garden (which is calculated as the sum of the beauty of each tree). He visits Jett's store to buy seeds for the $$$m$$$ trees but since Spring is just around the corner, the store is running low on some types of trees. For the $$$i$$$th type of tree at Jett's store, there are $$$t_i$$$ seeds of that type and each of those trees has a beauty of $$$b_i$$$. Given this information, help Phoneix figure out the maximum beauty he can construct for his garden.

The first line of the input will contain $$$n$$$ $$$(1 \le n \le 100)$$$, the number of types of trees, and $$$m$$$ $$$(1 \le m \le 10^5)$$$, the size of Phoenix's garden, or the number of trees he can pick out.

The next $$$n$$$ lines each contain two integers $$$t_i$$$ $$$(1 \le t_i \le 2000)$$$, and $$$b_i$$$ $$$(1 \le b_i \le 1000)$$$, where $$$t_i$$$ is the amount of the $$$i^{th}$$$ tree that is available, while $$$b_i$$$ is the beauty points one tree of that type would bring.

A single integer representing the maximum amount of beauty points Phoenix can acquire for his garden.

3 8
5 4
4 6
3 5

43

In the sample, Phoenix can take all $$$4$$$ seeds with beauty of $$$6$$$, all $$$3$$$ seeds with beauty of $$$5$$$, and one seed with beauty of $$$4$$$ to get the maximum possible beauty of $$$43$$$.