题目描述

Yuzu 开学了，但是她实在是很想打游戏。

Yuzu 她的课表上总共有 $n$ 节课，第 $i$ 节课的科目编号为 $a_i$（$1 \le a_i \le k$）。作为一个柚子，Yuzu 的上下文切换有一定开销。具体而言，她从第 $i$ 节课切换到第 $i+1$ 节课要承受 $c(a_i,a_j)$ 的代价。由于她实在是很想打游戏，她打算翘掉一些科目的所有课。

Yuzu 可以翘掉任意多门科目的课，也可以不翘任何课。如果 Yuzu 要翘掉科目 $i$ 的课，那么她会将课表中所有科目 $i$ 的课全部删除，但是翘课会有负罪感，所以她会获得 $t(i)$ 的代价。

Yuzu 有一个承受代价的上限 $L$，这样的话她就有足够的空闲时间打游戏。现在她想知道，有多少种不同的课表可以通过上述的翘课操作得到，且存在一种翘课方案使得总代价 $\le L$。

由于 Yuzu 不想完全荒废学业，她的课表里必须有至少一节课。

例如：假设 Yuzu 的课表是 $[1,1,4,5,1,4]$，那么她要承受的总代价为 $c(1,1)+c(1,4)+c(4,5)+c(5,1)+c(1,4)$。如果翘掉科目 $4$ 的所有课，那么她的新课表是 $[1,1,5,1]$，且要承受的总代价为 $c(1,1)+c(1,5)+c(5,1)+t(4)$。翘掉科目 $3,4$ 的所有课也可以得到同样的课表，但是总代价会额外增加 $t(3)$。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行三个正整数 $n,k,L$，代表 Yuzu 的课表长度、学校开设的科目数量、Yuzu 最大能够承受的代价；
• 接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 节课的编号；
• 接下来一行 $k$ 个整数，第 $i$ 个整数 $t(i)$ 代表翘掉科目 $i$ 的所有课的代价。
• 接下来 $k$ 行，每行 $k$ 个整数，第 $i$ 行第 $j$ 个整数为 $c(i,j)$，代表从科目 $i$ 切换到科目 $j$ 的代价；

输出格式

对于每组数据，输出一行一个整数，代表总代价不超过 $L$ 的方案数。

1
6 5 5
1 1 4 5 1 4
1 2 3 4 5
2 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 2
0 1 1 1 1

2

样例解释 1

• 翘掉科目 $1$ 的所有课，新课表为 $[4,5,4]$，总代价为 $c(4,5)+c(5,4)+t(1) = 2+1+1 = 4$；
• 翘掉科目 $1,4$ 的所有课，新课表为 $[5]$，总代价为 $t(1)+t(4) = 1+4 = 5$。

可以证明只有这两种方案的总代价不超过 $5$。

数据范围

• 对于 $30\%$ 的数据，$n \le 10^3$，$k \le 12$；
• 对于 $60\%$ 的数据，$k \le 15$；
• 对于 $100\%$ 的数据，$1 \le T \le 5$，$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 20$，$1 \le L \le 10^9$，$1 \le t(i),c(i,j) \le 10^9$。