题目描述

Recently, a job for an algorithms specialist opened up at NIH. You never thought you’d be using your expertise in algorithms to save lives, but now, here is your chance! While the doctors are very good in carrying out medical research and coming up with better cures for diseases, they are not so good with numbers. This is where you come in.

You have been tasked to allocate money for all disease research at NIH. The interesting thing about disease research is that the number of lives saved doesn’t linearly increase with the amount of money spent, in most cases. Instead, there are “break-points”. For example, it might be the case that for disease A, we have the following break-points:

If you spend more money than one breakpoint and less than another, the number of lives saved is equal to the amount saved for the previous breakpoint. (In the above example, if you spent $150 million, you’d still only save 1000 lives, and if you spent any amount more than $250 million, you’d still save 1100 lives.)

The doctors have figured out charts just like this one for all the diseases for which they do research. Given these charts, your job will be to maximize the number of lives saved spending no more than a particular budget.

The Problem:

Given several charts with information about how much has to be spent to save a certain number of lives for several diseases and a maximum amount of money you can spend, determine the maximum number of lives that can be saved.

输入格式

The first input line contains a positive integer, n (n ≤ 100), indicating the number of budgets to consider. The first line of each budget contains two positive integers, d (d ≤ 10), representing the number of diseases for which there is data and B (B ≤ 100000), the total budget, in millions of dollars. The following d lines contain information about each of the d diseases. Each of these lines will contain exactly four ordered pairs of positive integers separated by spaces. Each pair will represent a dollar level (in millions) followed by the number of lives saved for that dollar level of funding. Each of the pairs will be separated by spaces as well. Each of these values will be less than or equal to 100,000. Assume that the dollar levels on an input line are distinct and in increasing order, and that the number of lives saved on an input line are also distinct and in increasing order.

输出格式

For each test case, just output a line with the following format:

Budget #k: Maximum of x lives saved. where k is the number of the budget, starting at 1, and x is the maximum number of lives saved in that budget. Leave a blank line after the output for each test case.

样例

样例输入

3
2 2000
10 5 50 100 100 1000 250 1100
100 1 200 2 300 3 1900 1000
3 100
10 100 40 200 70 300 100 500
5 1 25 2 35 3 50 4
200 10000 300 20000 400 30000 500 40000
1 10
100 2 200 3 300 5 400 6

样例输出

Budget #1: Maximum of 2000 lives saved.

Budget #2: Maximum of 500 lives saved.

Budget #3: Maximum of 0 lives saved.