(自创，征集题目意见)超越无极之剑

题目描述：

小ET最近在玩 Terraria，他历经千辛万苦，终于凑齐了合出天顶剑的所有原材料，他兴致勃勃的去合成天顶剑。可是他发现，某些原材料是互斥的。在无数次的失败重来后，小ET终于找出了所有互斥的原材料........结果他发现需要把所有原材料组装成几把剑，再合成天顶剑，可是几把剑之间也有互斥的啊！！！

小ET一共有 $n$ 块原材料，每块原材料都有自己的战力，第 $i$ 块原材料的战力为 $f_i$，编号为 $i$。一把剑的战力为打造它的所有原材料的战力之和。同时有 $m$ 对原材料互斥，第 $i$ 对互斥的材料的编号分别是 ${c1}_i$ 和 $c2_i$，并且保证每对 $c1_i$ 和 $c2_i$ 互不相同。如果用第 $i$ 对互斥的材料打造一把剑，那么这把剑的总战力就会减去 $k_i$。现在要求你用这 $n$ 块原材料打造出刚好 $s \ (1 \le s \le n)$ 把剑，再用它们合出天顶剑。但是如果两把剑使用的制作材料中分别有一块材料并且这两块材料互斥，那么这两把剑也是互斥的。最终合出天顶剑时需要 $p \ (p \le s)$ 把剑，天顶剑的战力为合成它的所有剑战力之和，剩下的剑需要给小ET练练手。这 $p$ 把剑中，每对互斥的剑如果都用于合成了天顶剑，那么最终天顶剑的战力就会减去这两把剑中那对互斥的材料所扣除的战力。

通俗来讲，就是对于一对用于合成天顶剑的互斥的剑 $a_i,b_i$，如果让它们互斥的那对材料是第 $i \ (1 \le i \le m)$ 对，那么则最终合出天顶剑时，总战力会减去 $k_i$。

为了方便起见，小ET想在打造两把互斥的剑时，在两把剑中最多只能有一对互斥的材料，这也就意味着可能不能打造够 $s$ 把剑。如果不够打造出 $s$ 把剑，输出 -1。

现在小ET找到了你，想让你告诉他他能打造出来的天顶剑最大战力是多少。

输入描述：

第一行，四个正整数 $n,m,s,p$。

第二行，$n$ 个正整数 $f_1,f_2 \cdots f_n$，$f_i$ 代表编号为 $i$ 的原材料的战力。

接下来 $m$ 行，每行三个正整数 $c1_i,c2_i,k_i$，表示第 $i$ 对互斥的材料的编号与它们用在同一把剑里会减少的战力。

输出描述：

一行一个整数，表示能打造出来的天顶剑最大战力是多少。如果不够打造出 $s$ 把剑，输出 -1。

样例输入1：

5 2 3 2
2 4 3 8 7
1 2 1
4 5 2

样例输出1：

20

提示 / 说明：

样例1解释：

能够打造的三把剑的最好方案是 1, 2-4, 3-5，这样三把剑的战力就分别是 2, 12, 10，选择第二、三把剑，由于两把剑中有一对互斥的材料 4-5，所以最终战力减去 $2$，最大战力为 $20$。

数据范围：

$1 \le c1_i,c2_i \le n,m,s,p \le 1000$

$1 \le m \le \lfloor \dfrac{n}{2} \rfloor$

$1 \le p \le s \le n$

$1 \le f_i,k_i \le 10^5$

写在最后：

qwq 各位大佬求提意见如果有好的做法请在下方评论，有数据或其他地方不合理的也请提出，谢谢！

（阿巴阿巴作者也是写着玩的 所以才发到灌水区 请不要抄袭哦 [ :) ] ）