Curio Business Profit Maximization

FJ has entered the curio business. He has a catalog of N different cow curios (1 ≤ N ≤ 100) and an investment capital of M money (1 ≤ M ≤ 100,000). For each curio type i, the cost is given as \(C_i\) (1 ≤ C_i ≤ 100,000) and the revenue earned per sale is \(R_i\) (1 ≤ R_i ≤ 100,000), resulting in a profit of \(R_i - C_i\) for each curio sold.

FJ can purchase as many curios of each type as he wishes subject to his total spending not exceeding M. Note that some curios may not yield any profit (or even a loss) if \(R_i \le C_i\); such items need not be purchased. His goal is to maximize the total profit given by:

[ \text{profit} = \sum_{i=1}^{N} (R_i - C_i) \times x_i ]

subject to:

[ \sum_{i=1}^{N} C_i \times x_i \le M ]

where \(x_i\) is the number of curios of type \(i\) purchased. For instance, if FJ has 3 types of curios with M = 17 and the following cost-revenue structure:

• Curio 1: cost = 2, revenue = 4 (profit = 2)
• Curio 2: cost = 5, revenue = 6 (profit = 1)
• Curio 3: cost = 3, revenue = 7 (profit = 4)

Then the optimal strategy is to buy 5 of curio type 3 (cost = 15, profit = 20) and 1 of type 1 (cost = 2, profit = 2), achieving a total profit of 22.

Your task is to compute the maximum profit FJ can achieve.

inputFormat

The first line contains two integers N and M, where 1 ≤ N ≤ 100 and 1 ≤ M ≤ 100,000. The following N lines each contain two integers \(C_i\) and \(R_i\), representing the cost and revenue of the i-th curio.

outputFormat

Output a single integer representing the maximum total profit achievable by purchasing curios without exceeding the investment amount M.

sample

3 17
2 4
5 6
3 7

22