Problem C: Envelopes |
Please help me choose envelopes so that the total amount I need to spend in buying them is minimized.
The input may contain multiple test cases.
The first line of each test case contains two integers M ( ) and N ( ) where M is the number of greeting cards and N is the number of envelopes to choose from. The ith ( ) of the next M lines consists of two integers li and wi ( ) giving the dimensions of the ith greeting card. The ith ( ) of the next N lines contains three integers Li, Wi and Ci ( ) where Li and Wi give the dimensions of the ith envelope and Ci is its price in Taka.
The input terminates with two zeros for M and N.
For each test case in the input first print the test case number on a separate line as shown in the sample output. If an envelope can be chosen for each of the greeting cards in the input, print one line for each where the ith line contains the number of the envelope (in the order given in the input) inside which the ith greeting card should be put. Otherwise, print ``cannot buy" on a line by itself. Note that if there are multiple solutions with minimum cost, any one of them is acceptable.
Print a blank line between two successive test cases.
2 4 105 9 99 149 110 10 10 100 50 5 150 100 7 90 140 15 1 2 100 150 99 149 10 142 100 5 0 0
Case #1 2 3 Case #2 cannot buy