商品摆放
题号：NC220677
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在一个超市里出售种商品，分别编号。
如果某两种商品摆放在相邻的位置上，他们可能会刺激顾客消费以带来额外收益（比如炸鸡便当和可乐）。
假设我们初始已经有了一个个商品的货架，每个货架的位置上都摆放着某个商品。假设你可以最多移除件商品，移除后原本不相邻的商品就会变的相邻，请问你可以获得最大的额外收益是多少呢？

输入描述:

第一行三个以空格分隔的整数。
第二行个以空格分隔的整数数组，表示初始的时候第个位置摆放着第种商品。
接下来的的矩阵，其中第行第列代表，表示这2种商品如果摆放在相邻位置会产生的额外收益。

输出描述:

输出一行，一个整数表示你可以获得的最大额外收益。
示例1

输入

复制 
4 1 3
1 4 2
0 3 0 1
3 0 0 0
0 0 0 0
1 0 0 0

输出

复制 
3

说明

如果不移除任何商品，则额外收益总和为w_{14}+w_{42}=1。
如果移除位置为2的商品，则额外收益综合为w_{12}=3。

备注:




保证=,