题目描述

小$A$想生成一个长度为n的排列。不同的排列会产生不同的收益，具体规则如下：

• 1，若在序列$A$的第$i$个位置填$j$（$A_i =j$），则会产生大小为$B_{i,j}$的收益。其中$B$将以矩阵形式作为输入给出。

• 2，若$A_x$与$A_y$的和大于$k$，则会产生大小为$P$的收益。其中$x$、$y$、$k$、$P$由输入数据给出。

最终的收益为排列$A$在规则$1$、$2$下的收益总和。

小$A$希望总收益最小。她想知道，最小的总收益是多少？

输入格式

第一行一个正整数$n$，其含义见题目描述。

接下来$n$行每行$n$个正整数，其中第$i$行第$j$个数$B_{i,j}$ 表示在序列$A$的第$i$个位置填$j$（$A_i =j$）的收益。

接下来一行，一个非负整数$Q$，表示规则$2$有$Q$组。

接下来Q行每行四个正整数，$x$、$y$、$k$、$P$。含义为若$A_x$ 与$A_y$ 的和大于$k$，则会产生大小为$P$的收益。

输出格式

输入只有一行，一个正整数，表示最小的总收益。

样例 #1

样例输入 #1

3
2 1 2 
2 1 2 
2 2 3 
2
3 2 2 2
3 2 1 3

样例输出 #1

10

样例 #2

样例输入 #2

4
3 3 3 3 
2 4 3 2 
1 1 1 3 
2 3 3 4 
2
3 1 3 4
2 3 1 3

样例输出 #2

12

【数据范围】

对于测试点1~5: $Q = 0$。

对于测试点6~10: $Q = 20$。

对于测试点1、6: $n \leq 6$。

对于测试点2、7: $n \leq 8$。

对于测试点3、8: $n \leq 10$。

对于测试点1~10：保证数据满足$1\leq x,y \leq n \leq 11$ 且$0 \leq k, B_{i,j} , P\leq 10^9$。