アメカーの部屋

时空限制#

C/C++: 4s/1024MB

其他语言：8s/1024MB

题目描述#

虽在小镇上最受欢迎的折纸咖啡馆工作，身为料理技艺高超的老板娘的女儿，织部心的料理水平却不尽人意，她的料理能让人「深刻地感受到自己是活着的」。

一天，在诚外出采购时，心为了犒劳自己亲爱的「哥哥」，心为诚做了一桌爱心午餐。

这份午餐有 $n$ 种料理，每份料理的美味值为 $w_i$ ，属性为 $c_i$ 。

不同料理之间的食材可能会发生相互作用。一共有 $m$ 组这样的关系。每组关系由三个整数 $(u_i, v_i, W_i)$ 描述，表示如果 同时吃下 第 $u_i$ 种和第 $v_i$ 种料理，那么会 额外获得 $W_i$ 的美味值。

在心的强烈要求下，诚必须：

• 至少 吃掉 $k$ 种料理
• 每种属性的料理都 至少 吃掉 $b$ 份。

为了尽可能保护自己的味觉，诚能从这顿午餐获得的最大总美味值是多少？

形式化地，设诚最终选择吃掉的料理集合为 $S$，则总美味值定义为：

你需要求出满足条件的集合 $S$ 的最大总美味值。

输入格式#

每个测试包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每组测试用例：

• 第一行包含四个整数 $n, m, k, b$ ($1 \le n \le 200$，$0 \le m < n$，$1 \le k \le n$，$0 \le b \le \lfloor \frac{k}{2} \rfloor$)，分别表示料理的数量，相互作用的料理组数，至少吃掉的料理数，每种属性至少吃掉的料理数。
• 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ( $-10^9 \le w_i \le 0$ )，表示每种料理的美味值。
• 第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($c_i \in \{0,1\}$，$b \le \sum c_i \le n-b$ )，表示每种料理的属性。
• 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, W_i$ ($1 \le u_i, v_i \le n$，$u_i \ne v_i$，$-10^9 \le W_i \le 0$ )，表示第 $u_i$ 种料理与第 $v_i$ 种料理之间存在一组相互作用。

保证由这 $m$ 组关系构成的无向图是一张森林¹。

保证所有测试用例中 $n$ 的总和不超过 $200$，所有测试用例中 $k$ 的总和不超过 $200$。

输出格式#

对于每组测试用例，输出一个整数，表示诚能够获得的最大总美味值

样例#

1
3
2
4 1 2 1
3
-1 -2 -3 -4
4
0 0 1 1
5
1 3 -5
6
5 3 3 1
7
-3 -2 -4 -1 -5
8
0 1 0 1 0
9
1 2 -2
10
2 3 -3
11
4 5 -1
12
6 3 5 2
13
-10 -8 -5 -1 -2 -4
14
0 0 1 1 1 1
15
1 2 -9
16
3 4 -5
17
5 6 -10

1
-5
2
-8
3
-40

说明/提示#

在第一个测试样例中，在满足至少选 $2$ 种且两种属性都至少选 $1$ 种的前提下，最优方案为选第 $1,4$ 种或第 $2,3$ 种料理，总美味值均为 $-5$ 。

「米饭和面包都是主食嘛，所以我觉得米饭拌草莓酱也会好吃。」

「要是只有甜味我觉得菜就会太单调了，所以稍微加了一些辣椒酱。」

「加了多少？嗯~~ 就把剩下的全加了？」

「『为了折纸的未来着想，这些料理一定不能端到客人面前。。。』」

「为什么要说这么坏心眼的话，呜呜~」