本题没有可用的提交语言。

题目描述

Dearboy最近忙得不可开交，攒了一堆衣服要洗。幸运的是，他有一个漂亮又勤劳的女朋友帮忙。这些衣服有各种颜色，但每件衣服都可以视为单一颜色。为了防止衣服混色染色，Dearboy和他的女朋友必须先洗完一种颜色的所有衣服，再开始洗另一种颜色的衣服。

根据经验，Dearboy知道每件衣服由一个人洗需要多长时间。每件衣服只能由Dearboy或他的女朋友中的一人清洗，两人可以同时洗两件衣服。求他们完成所有衣服清洗所需的最短时间。

输入格式

• 输入包含多个测试用例。每个测试用例以两个正整数 M 和 N（M < 10，N < 100） 开头，分别表示颜色种类数和衣服总数。
• 下一行包含 M 个不超过10个字符且不含空格的字符串，表示颜色名称。
• 接下来 N 行 描述每件衣服，每行包含一个整数（清洗时间，小于1000）和一个颜色名称。
• 最后以两个0结束输入。

输出格式

• 对每个测试用例，输出一行表示两人完成清洗所需的最短时间。

输入输出样例

输入数据 1

3 4  
red blue yellow  
2 red  
3 blue  
4 blue  
6 red  
0 0  

输出数据 1

10  

题目来源

POJ Monthly--2007.04.01, dearboy