New Year Discounts#2793
During the New Year's holiday season, the computer supermarket is offering a "New Year's Discounts" promotion. For each of the types of products available, both the regular and promotional prices are provided. Each product can only be purchased once. What is the maximum total discount you can obtain by spending no more than ?
The first line contains the numbers and . The following lines each contain two numbers representing the regular and promotional prices of the products. All values are natural numbers, M \leq 1000, and all other values do not exceed .
Output the maximum total discount possible.
Example 1