using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5");
WillReturn.Add("4");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4 5");
WillReturn.Add("4");
WillReturn.Add("1 2");
WillReturn.Add("1 3");
WillReturn.Add("1 4");
WillReturn.Add("1 5");
WillReturn.Add("3 1 4 1");
WillReturn.Add("5 9 2");
WillReturn.Add("6 5");
WillReturn.Add("3");
//9
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("3");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4 5");
WillReturn.Add("9 1 1 1");
WillReturn.Add("1 1 1");
WillReturn.Add("1 1");
WillReturn.Add("9");
//3
}
else if (InputPattern == "Input3") {
WillReturn.Add("5");
WillReturn.Add("3");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 4");
WillReturn.Add("4 5");
WillReturn.Add("5 4 4 4");
WillReturn.Add("4 4 4");
WillReturn.Add("4 4");
WillReturn.Add("5");
//5
}
else if (InputPattern == "Input4") {
WillReturn.Add("2");
WillReturn.Add("0");
WillReturn.Add("0");
WillReturn.Add("371");
//0
}
else if (InputPattern == "Input5") {
WillReturn.Add("8");
WillReturn.Add("13");
WillReturn.Add("1 8");
WillReturn.Add("5 7");
WillReturn.Add("4 6");
WillReturn.Add("1 5");
WillReturn.Add("7 8");
WillReturn.Add("1 6");
WillReturn.Add("1 2");
WillReturn.Add("5 8");
WillReturn.Add("2 6");
WillReturn.Add("5 6");
WillReturn.Add("6 7");
WillReturn.Add("3 7");
WillReturn.Add("4 8");
WillReturn.Add("15");
WillReturn.Add("3 5");
WillReturn.Add("1 7");
WillReturn.Add("4 6");
WillReturn.Add("3 8");
WillReturn.Add("7 8");
WillReturn.Add("1 2");
WillReturn.Add("5 6");
WillReturn.Add("1 6");
WillReturn.Add("1 5");
WillReturn.Add("1 4");
WillReturn.Add("2 8");
WillReturn.Add("2 6");
WillReturn.Add("2 4");
WillReturn.Add("4 7");
WillReturn.Add("1 3");
WillReturn.Add("7483 1694 5868 3296 9723 5299 4326");
WillReturn.Add("5195 4088 5871 1384 2491 6562");
WillReturn.Add("1149 6326 2996 9845 7557");
WillReturn.Add("4041 7720 1554 5060");
WillReturn.Add("8329 8541 3530");
WillReturn.Add("4652 3874");
WillReturn.Add("3748");
//21214
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
int NodeCnt = int.Parse(InputList[0]);
int UB = NodeCnt - 1;
int MG = int.Parse(InputList[1]);
int[,] HasEdgeArr1 = new int[UB + 1, UB + 1];
int[,] HasEdgeArr2 = new int[UB + 1, UB + 1];
int[,] CostArr = new int[UB + 1, UB + 1];
foreach (string EachStr in InputList.Skip(2).Take(MG)) {
SplitAct(EachStr);
int FromNode = wkArr[0] - 1;
int ToNode = wkArr[1] - 1;
HasEdgeArr1[FromNode, ToNode] = 1;
HasEdgeArr1[ToNode, FromNode] = 1;
}
int MH = int.Parse(InputList[1 + MG + 1]);
foreach (string EachStr in InputList.Skip(2 + MG + 1).Take(MH)) {
SplitAct(EachStr);
int FromNode = wkArr[0] - 1;
int ToNode = wkArr[1] - 1;
HasEdgeArr2[FromNode, ToNode] = 1;
HasEdgeArr2[ToNode, FromNode] = 1;
}
int CurrY = 0;
foreach (string EachStr in InputList.Skip(2 + MG + 1 + MH)) {
int[] CurrArr = EachStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
for (int CurrX = 0; CurrX <= CurrArr.GetUpperBound(0); CurrX++) {
int FromNode = CurrY;
int ToNode = CurrX + CurrY + 1;
CostArr[FromNode, ToNode] = CurrArr[CurrX];
CostArr[ToNode, FromNode] = CurrArr[CurrX];
}
CurrY++;
}
var BaseList = new List<int>();
for (int I = 0; I <= UB; I++) {
BaseList.Add(I);
}
var AnswerList = new List<long>();
foreach (int[] EachArr in RubyPatternClass<int>.Permutation(BaseList, BaseList.Count)) {
long Answer = 0;
// 全部の辺をチェック
for (int I = 0; I <= UB; I++) {
for (int J = 0; J <= UB; J++) {
int NewI = EachArr[I];
int NewJ = EachArr[J];
if (NewI == NewJ) continue;
if (HasEdgeArr1[I, J] != HasEdgeArr2[NewI, NewJ]) {
Answer += CostArr[NewI, NewJ];
}
}
}
AnswerList.Add(Answer);
}
// 二重で計上してるので、2で割る
Console.WriteLine(AnswerList.Min() / 2);
}
}
#region RubyPatternClass
// Rubyの場合の数
internal static class RubyPatternClass<Type>
{
// 順列を返す
private struct JyoutaiDef_Permutation
{
internal List<int> SelectedIndList;
}
internal static IEnumerable<Type[]> Permutation(IEnumerable<Type> pEnum, int pR)
{
if (pR == 0) yield break;
Type[] pArr = pEnum.ToArray();
if (pArr.Length < pR) yield break;
var Stk = new Stack<JyoutaiDef_Permutation>();
JyoutaiDef_Permutation WillPush;
for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
WillPush.SelectedIndList = new List<int>() { I };
Stk.Push(WillPush);
}
while (Stk.Count > 0) {
JyoutaiDef_Permutation Popped = Stk.Pop();
// クリア判定
if (Popped.SelectedIndList.Count == pR) {
var WillReturn = new List<Type>();
Popped.SelectedIndList.ForEach(X => WillReturn.Add(pArr[X]));
yield return WillReturn.ToArray();
continue;
}
for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
if (Popped.SelectedIndList.Contains(I)) continue;
WillPush.SelectedIndList = new List<int>(Popped.SelectedIndList) { I };
Stk.Push(WillPush);
}
}
}
}
#endregion