1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10670 (Work Reduction)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1611
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.0, 05/24/2009
*
* Status : Accepted
* Runtime: 0.396
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Map.Entry;

@SuppressWarnings("unchecked")
class Main
{

public static void main(String[] args) throws IOException
{
//set up all variables needed
StringBuilder bu = new StringBuilder();
BufferedReader Reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer;
String line, name;
int amount, current, goal, costOne, costHalf, change, sum;
int current_work, tmp;
Map<String, Integer> result;

//read-in amount of test cases
line = read(Reader);
amount = Integer.parseInt(line);

for(int i=1;i<=amount;i++)
{
line = read(Reader);
tokenizer = new StringTokenizer(line);
result = new HashMap<String, Integer>();

//set current workload and target workload
current = Integer.parseInt(tokenizer.nextToken());
goal = Integer.parseInt(tokenizer.nextToken());

//get though agencies
for(int j=Integer.parseInt(tokenizer.nextToken());j>0;j--)
{
line = read(Reader);
tokenizer = new StringTokenizer(line," ,:");

//set agency values
name = tokenizer.nextToken();
costOne = Integer.parseInt(tokenizer.nextToken());
costHalf = Integer.parseInt(tokenizer.nextToken());

//how many steps are needed until costHalf is cheaper than single Cost
change = (int) Math.ceil(((double)costHalf) / costOne);
current_work = current;
sum = 0;

//calculate costs for agency
while(current_work > goal)
{
tmp = current_work;
tmp >>= 1;

if(tmp >= goal)
{
if((current_work-tmp)>change || ((current_work-tmp)==change && costHalf<costOne))
{
sum += costHalf;
current_work = tmp;
}
else
{
sum += (current_work-goal)*costOne;
current_work = goal;
}
}
else
{
sum += (current_work-goal)*costOne;
current_work = goal;
}

}

result.put(name, sum);
}

//sort by value
result = sortByValue(result);

//add answer
bu.append("Case " + i + "\n");

for(Entry<String, Integer> set : result.entrySet())
{
bu.append(set.getKey() + " " + set.getValue() + "\n");
}
}

//print result
System.out.print(bu.toString());
}

/**
* sortByValue
*
* This methods sorts a map by its values.
*
* @param map: map to be sorted by value
* @return ordered map.
*/
public static Map sortByValue(Map map)
{
List list = new LinkedList(map.entrySet());
Collections.sort(list, new Comparator()
{
/**
* compare
*
* Compares the values of two EntrySets. If values are equal, it's sorted
* by the key.
*
* @param o1: Object, obviously an EntrySet
* @param o2: Object, obviously an EntrySet
* @return int: positive, negative (greater or smaller) or zero (equal)
*/
public int compare(Object o1, Object o2)
{
if (((Comparable) ((Map.Entry) (o1)).getValue())
.compareTo(((Map.Entry) (o2)).getValue())==0)
return ((Comparable) ((Map.Entry) (o1)).getKey())
.compareTo(((Map.Entry) (o2)).getKey());
return ((Comparable) ((Map.Entry) (o1)).getValue())
.compareTo(((Map.Entry) (o2)).getValue());
}
});

Map result = new LinkedHashMap();
for (Iterator it = list.iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry)it.next();
result.put(entry.getKey(), entry.getValue());
}
return result;

}


/**
* reader
*
* This methods reads from a BufferedReader and skips over empty lines
*
* @param reader: A BufferedReader
* @return the next String returned by reader
* @throws IOException
*/
public static String read(BufferedReader reader) throws IOException
{
String read = reader.readLine();
while(read.isEmpty())
read = reader.readLine();

return read;
}
}