假期旅行团（Vacation Tours）

题目背景

一家旅行社正在为一群住在同一家酒店的游客安排观光旅行。

每次旅行都会从酒店出发，游览若干景点后再回到酒店。为了避免游客重复参观同一个地方，不同旅行之间不能包含相同的景点。

旅行社每组织一次旅行，都会向整个旅行团收取一笔固定费用。与此同时，旅行社还需要承担酒店与景点之间、以及不同景点之间的交通费用。

请帮助旅行社安排若干次旅行，使最终收益最大。

题目描述

共有 $N$ 个地点，编号为：

$$0,1,\ldots,N-1.$$

其中：

• 地点 $0$ 是酒店；
• 地点 $1$ 到 $N-1$ 是景点。

一次旅行由一个非空的景点序列：

$$v_1,v_2,\ldots,v_k$$

构成，并按照以下路线行进：

$$0\to v_1\to v_2\to\cdots\to v_k\to 0.$$

一次旅行中的景点必须两两不同。

旅行社可以安排任意多次旅行，也可以一次旅行都不安排。所有被安排的旅行还必须满足：

• 每个景点至多出现在一次旅行中。

也就是说，游客不能在不同旅行中重复参观同一个景点。并不要求所有景点都必须被参观。

每安排一次旅行，旅行社都会收取固定费用 fee。

交通是有向的。从地点 $i$ 到地点 $j$ 的费用记为：

$$cost_{i,j}.$$

通常情况下：

$$cost_{i,j}\ne cost_{j,i}.$$

此外，交通费用不保证满足三角不等式。当路线要求从地点 $i$ 前往地点 $j$ 时，必须直接支付 $cost_{i,j}$，即使经过其他地点会更加便宜，也不能用间接路线代替。

若一次旅行依次游览 $v_1,v_2,\ldots,v_k$，则其交通成本为：

$$cost_{0,v_1} +\sum_{i=1}^{k-1}cost_{v_i,v_{i+1}} +cost_{v_k,0}.$$

设一共安排了 $r$ 次旅行，所有旅行的交通成本之和为 $C$，则旅行社的收益为：

$$r\times fee-C.$$

请计算旅行社能够获得的最大收益。

由于可以选择不安排任何旅行，因此答案至少为 $0$。

交通费用的编码方式

交通费用使用两个 Base64 字符进行编码。

输入给出两个 $N\times N$ 的字符矩阵 $c$ 和 $d$。从地点 $i$ 到地点 $j$ 的交通费用为：

$$cost_{i,j}=value(c_{i,j})\times 64+value(d_{i,j}).$$

字符对应的数值如下：

字符范围	数值
A 到 Z	$0$ 到 $25$
a 到 z	$26$ 到 $51$
0 到 9	$52$ 到 $61$
+	$62$
/	$63$

例如：

• A 的值为 $0$；
• B 的值为 $1$；
• a 的值为 $26$；
• 0 的值为 $52$；
• / 的值为 $63$。

若某项的两个编码字符分别为 B 和 J，则对应费用为：

$$1\times64+9=73.$$

输入格式

第一行包含两个整数 $N$ 和 fee，分别表示地点总数和每次旅行收取的固定费用。

接下来 $N$ 行，每行包含一个长度为 $N$ 的字符串，依次描述矩阵 $c$。

随后 $N$ 行，每行包含一个长度为 $N$ 的字符串，依次描述矩阵 $d$。

字符串中的字符均为题目规定的 Base64 编码字符。

输出格式

输出一个整数，表示旅行社能够获得的最大收益。

数据范围

对于所有测试数据：

• $2\le N\le 50$；
• $1\le fee\le 10000$；
• 矩阵 $c$ 和 $d$ 均有 $N$ 行；
• 每一行的长度均为 $N$；
• 所有字符均属于：
  • A 到 Z；
  • a 到 z；
  • 0 到 9；
  • +；
  • /；
• 对于所有 $0\le i<N$，$c_{i,i}$ 和 $d_{i,i}$ 均为 A。

样例 1

输入

3 15
AAA
AAA
AAA
ABJ
JAB
BJA

输出

12

解释

解码后的交通费用矩阵为：

- 1 9
9 - 1
1 9 -

一种方案是分别安排只参观景点 $1$ 和景点 $2$ 的两次旅行。

两次旅行的成本均为 $10$，总收费为：

$$15\times2=30,$$

因此收益为：

$$30-20=10.$$

更优的方案是只安排一次旅行：

$$0\to1\to2\to0.$$

其交通成本为：

$$1+1+1=3,$$

因此收益为：

$$15-3=12.$$

样例 2

输入

4 100
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA
AAAA

输出

300

解释

所有交通费用均为 $0$。

分别为三个景点各安排一次旅行，可以安排 $3$ 次旅行并获得：

$$3\times100=300$$

的收益。

样例 3

输入

3 1000
A//
/A/
//A
A//
/A/
//A

输出

0

解释

所有可能的旅行成本都过高，因此最优方案是不安排任何旅行。

样例 4

输入

7 1000
AAA////
/AA/A//
//AA/A/
A//AA//
///AAA/
///A/AA
AA////A
AKo////
/AU/X//
//AZ/o/
j//AK//
///XAo/
///y/AK
KP////A

输出

1809

样例 5

输入

2 1
AA
AA
AA
AA

输出

1