题目描述

城市中有 ( M ) 条主要街道，连接着 ( N ) 个路口。每个路口 ( i ) 有风力计示数 ( v_i )，每条街道 ( i ) 有狭管效应强度 ( e_i )。

需选择一个由不超过 ( K ) 条街道（无重复）组成的集合 ( S )，最大化以下值：

其中 ( I(S) ) 是与 ( S ) 中至少一条街道相连的所有路口的集合（重复连接的路口仅算一次）。

输入格式

第一行一个正整数 ( T )，表示测试点个数。对每个测试点：

• 第一行三个正整数 ( N, M, K )，分别表示路口数、街道数、选取街道数量上限。
• 第二行 ( N ) 个非负整数，为 ( v_1, v_2, \cdots, v_N )。
• 接下来 ( M ) 行，每行三个整数 ( a_i, b_i, e_i )，表示街道 ( i ) 连接路口 ( a_i ) 与 ( b_i )，效应强度为 ( e_i )。

输出格式

对每个测试点输出一行一个整数，表示最大值。

样例

• 输入：

  1
  5 5 2
  1 2 4 8 16
  1 2 1
  1 3 2
  3 4 2
  4 5 2
  2 5 1
  

• 输出：

  27
  

• 解释：选择街道 (2,5) 和 (3,4)，( \sum e_i = 1 + 2 = 3 )。( I(S) = {2,3,4,5} )，( \sum v_i = 2 + 4 + 8 + 16 = 30 )。总价值：( 30 - 3 = 27 )。

数据范围与提示

• 对所有数据：( \sum 2^K (N + M) \leq 10^6 )，( 1 \leq T \leq 5 )，( 1 \leq N, M, K )，( 0 \leq e_i, v_i \leq 10^8 )，( 1 \leq a_i, b_i \leq N )。
• 图可以有重边、不连通、孤立点，无自环。
• 答案不超过 ( 2 \times 10^9 )。

子任务 1

• 分值：$30$ 分
• 限制条件：$\sum (N+M) \leq 1500$

子任务 2

• 分值：$30$ 分
• 限制条件：$K \leq 9$

子任务 3

• 分值：$40$ 分
• 限制条件：无额外限制