题目描述
Spore中用以代表经济的是一种叫做“香料矿”的矿物。香料矿有不同的种类，可以由它们的颜色轻易区分开来。
火星怪兽已经控制了一些星系，并且在这些星系上建立了殖民地来开采香料矿。由于每个殖民地储存开采出来的香料的能力是有限的，在一次远征任务完成之后，火星怪兽发现他所有殖民地的香料库都满了，无法继续开采。为了不浪费时间，他决定把所有的香料都运回母星进行处理。
火星怪兽的母星上有一座香料处理工厂，它有两台处理机，所以可以同时处理两批香料。但是不同的香料一起进入工厂是会出现危险的，所以这座工厂的两台处理机同一时刻处理的香料必须是相同种类的。
现在有M种香料，共N批($M <= 10, N <= 100$)，每一批香料所的种类及其需要的处理时间都是已知的。对于每一批香料，你可以选择由两台机器的任何一台来处理。你的任务是帮助火星怪兽确定一个处理方案，以在最短的时间内处理完所有香料，好给他腾出一点时间去看最近更新的宅男动漫。

•输入格式

输入数据包含了多个测试点。每一个测试点格式如下：
第一行，两个由空格分开的整数，分别代表M、N。
第二行，M个由空格隔开的字符串，长度均不超过10，为各种香料的名称。
以下N行，每行一个整数Ti($0 输入文件以M=0、N=0结束。

•输出格式

对于每个测试点，输出一行，仅包含一个整数，代表最少所需要的时间。

•输入样例

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

•输出样例

10