小红的双生英雄
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小红有 n 个英雄,第 i 个英雄的 cost 是 a_i,战斗力为 b_i。另外,存在一些“双生英雄”关系,如果同时上阵某一对英雄,则可以获得额外的战斗力收益。
\hspace{15pt}现在小红最多可以上阵四名英雄,且要求总 cost 不超过C。小红希望你求出组队的最大战斗力。

输入描述:

\hspace{15pt}第一行输入三个整数 n,C,m \left(1 \leqq n,C \leqq 10^3;\ 0 \leqq m \leqq n/2\right) 代表英雄数量、总cost限制、双生英雄的对儿数。 
\hspace{15pt}此后 n 行,第 i 行输入两个正整数 a_i,b_i \left(1 \leqq a_i,b_i \leqq 10^9\right) 代表第 i 个英雄的 cost 和战斗力。
\hspace{15pt}此后 m 行,第 i 行输入三个正整数 u_i,v_i,w_i \left(1 \leqq u_i,v_i \leqq n; u_i \neq v_i; 1 \leqq w_i \leqq 10^9\right) 代表第 u_i 和第 v_i 个英雄是双生英雄,同时上阵可以额外增加 w_i 战斗力。

\hspace{15pt}除此之外,保证每个英雄最多只存在一对双生英雄关系。对于 40\% 的用例,额外保证 m=0

输出描述:

\hspace{15pt}输出一个整数,代表组队的最大战斗力。
示例1

输入

复制
4 10 1
3 9
4 10
6 15
8 20
1 2 15

输出

复制
34

说明

\hspace{15pt}在这个样例中,小红可以选择上阵第一、二个英雄,获得 9+10+15=34 的战斗力。我们可以证明,这是符合要求的最大战斗力。
示例2

输入

复制
4 1 1
3 9
4 10
6 15
8 20
1 2 15

输出

复制
0