背景

由于小萌萌很可爱，有 N (1 ≤ N ≤ 180) 个小朋友争着要抱萌萌，但是因为没有那么多的时间让所有小朋友都抱过萌萌，而且在争抢过程中也许会伤害到萌萌，所以绵羊爸爸精心制作了 N 个情态各异的萌萌布娃娃，来分给这N个小朋友。

描述

绵羊爸爸把这些布娃娃交给其中几个小朋友，然后由小朋友们自己传递布娃娃。每个布娃娃对小朋友们都有一个吸引度，我们规定布娃娃的吸引度在数值上等于小朋友对这个布娃娃的喜爱程度，而在传递过程中布娃娃对小朋友们的吸引度会相应地下降。但是如果某个布娃娃对分到它的小朋友的吸引度太高了，他会不归还布娃娃，所以绵羊爸爸规定小朋友们，在吸引度下降最少的前提下，得到的分配方案中，对分到的布娃娃最喜爱的那个小朋友，他的喜爱程度要尽可能地小。注意：每个小朋友都可以传递多个布娃娃，最终每个小朋友都应该得到一个布娃娃。

格式

输入格式

第一行两个整数N,P (1 ≤ N ≤ 180)，代表了共有 N 位小朋友想要萌萌布娃娃。

第二行有 N 个正整数，第i个数表示第i个布娃娃对小朋友们的吸引度。

第三行有N个1~N的正整数，第i个数x表示绵羊爸爸一开始将第i个布娃娃交给了第x个小朋友。

第三至 N+2 行是N 位小朋友的名字，无多余的空格（无需检验数据正确性）。

接下来的 N 行，每行有 N 个正整数。第N+2+i 行的第 j 个数表示第 i 个小朋友把布娃娃传递给第 j 个小朋友时这个布娃娃下降的吸引度。现在你需要找到一个合适的分配方案，使得这个方案中满足绵羊爸爸的要求。涉及到的数字（及中间过程）的绝对值均在50,000,000范围内。数据保证方案唯一。

输出格式

输出文件的第一行，表示方案中的最大喜爱程度。

接下来的 N 行，每行有一个字符串 S ，表示第 i 个布娃娃被分给了名字是 S 的小朋友。

样例1

样例输入1

3
10 8 6
1 1 1
yuhc
brace
jcw123
1 2 3
4 5 6
7 8 9

样例输出1

7
jcw123
brace
yuhc

限制

所有测试点时限均为1000ms

提示

“吸引度下降最少的前提下”如何理解：比如在一个方案中，1那里的布娃娃最后要传到3，那么传递过程中这个布娃娃就按照减少最少的路径传递。

来源

2009年江中信奥模拟赛