当前没有测试数据。

题目描述

    某校新建的大楼中有n台设备，学校需要利用这些设备搭建一个网络。我们用1到n的整数给这些设备编号。

    这些设备之间一共可以建立m条连线，建立每条连线会消耗一定的费用。连接建立后两台设备就可以相互通信了。两台设备可以借助其他设备进行通信，即通信关系可传递：如果设备A和设备B都能与设备C相互通信，那么设备A和设备B也能相互通信。

    由于大楼的拓扑结构所限，可以建立连线的两台设备，一定满足其编号之差的绝对值不超过p。

    这n台设备中的一部分属于用户设备。学校要求在最终的网络中，用户设备必须两两能够相互通信，其他设备则可以根据需要选择连线或不连线。

    现在问要达到学校的要求最少要消耗多少的费用。

输入格式

    输入的第一行包含一个正整数T，表示数据的组数，保证T=5。接下来依次描述每组数据。

    每组数据的第一行包含3个正整数n, m, p，表示设备的总数，可以建立的连线数量和拓扑结构的参数。

    第二行包含一个长度为n的01字符串，依次表示这n台设备是否为用户设备；为1表示是，为0表示不是。相邻字符之间无空格隔开，保证不会出现除了0和1之外的字符。保证至少有2个设备是用户设备。

    接下来m行，每行包含3个非负整数u, v, w，表示设备u和设备v可以消耗w的费用建立连线。其中0 < u < v ≤ n，v – u ≤ p，w ≤ 106。

    除第二行外，所有的数之间用一个空格隔开。

    保证两台设备之间最多只有一条可以建立的连线，保证至少存在一种方案能够满足学校的要求。

输出格式

对于每组数据，输出一行一个整数，表示能达到要求所需的最少费用。

样例

1
20 11 6
10000100001100000000
1 6 300
1 3 100
3 6 100
4 10 100
4 6 100
6 10 400
10 15 100
11 15 100
10 11 500
12 15 100
15 20 100

700

解释#1

用户设备分别是1、6、11、12。最优的方案需要选择以下连线：设备1和3，费用100；设备3和6，费用100；设备4和6，费用100；设备4和10，费用100；设备10和15，费用100；设备11和15，费用100；设备12和15，费用100。共计700。

子任务

每个测试点的每组数据分别都满足以下限制（其中c表示用户设备总数）：

编号	n	p	c
1	=500	=6	=n
2			=2
3			=4
4			=6
5			=10
6		=2	无限制
7
8		=3
9		=6
10