U106905 D5T1 问世间 是否此山最高

> 我刚开始想你就给我猜结论，滚！——张之洞

xuanxuan001 发现了 $n$ 块魔石，第 $i$ 块魔石有 $w_i$ 的质量和 $v_i$ 的魔力。xuanxuan001 可以带走的魔石的质量和最大为 $m$。另外他发现魔石之间还有 $k$ 种增益组合，每种组合效果用一个三元组 $(i,j,v)$ 表示，意思是如果同时选择了第 $i$ 块和第 $j$ 块魔石，就能额外增加 $v$ 的魔力（**注：组合之间不互斥，效果可以累加**），求他能带走的最大魔力。

输入数据共 $1+n+k$ 行。 第一行共三个整数 $n$，$m$，$k$，分别表示魔石的数量，xuanxuan001 能带走的最大质量和以及增益组合的个数。 之后 $n$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 块魔石的质量和魔力。 之后 $k$ 行，每行三个整数 $i$，$j$，$v$，表示如果同时选择了第 $i$ 块和第 $j$ 块魔石，就能额外增加 $v$ 的价值。

仅一行一个整数，表示 xuanxuan001 能带走的最大魔力值。

#### 样例解释 样例一解释：选择第 $3,4$ 块魔石，魔力和为 $11$。 样例二解释：选择第 $1,4$ 块魔石，满足第 $1$ 种组合再加 $5$ 的魔力，魔力和为 $14$。 样例三解释：选择第 $2,4,5$ 块魔石，满足第 $1,3$ 种组合再加 $12$ 的魔力，魔力和为 $20$。 --- #### 数据范围 对于 $10\%$ 的数据，保证 $1 \le n \le 20$。 对于另外 $20\%$ 的数据，保证 $k=0$。 对于另外 $30\%$ 的数据，保证 $1 \le n \le 100$，$1 \le m \le 200$。 对于 $100\%$ 的数据，保证 $1 \le n \le 10^3$，$1 \le m \le 2 \times 10^3$，$0 \le k \le 10$，$1 \le w_i \le 300$，$1 \le i,j \le n$，$1 \le v \le 500$，$1 \le v_i \le 500$，$i \ne j$。