测试数据来自 system/3090

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H在闲逛珠宝店时，买到了一个中意的手镯。很自然地，他想从他收集的 \(N\) 块宝石中选出最好的那些镶在手镯上。对于第 \(i\) 块宝石，它的重量为 \(w_i\)，把它镶上手镯后能增加的魅力值为 \(p_i\)。由于小H能忍受的重量不能超过 \(V\)，所以他需要选择重量和不超过 \(V\) 的宝石，使魅力值之和达到最大。

　　但问题没那么简单，小H发现，在这 \(N\) 块宝石里有 \(M\) 对完全不同的宝石，如果将第 \(i\) 对宝石同时镶在手镯上，则魅力值会额外增加 \(c_i\)。

　　由于小H最近忙于学习图论知识，所以请你来帮忙选取一些宝石，使得把它们镶在手镯上后增加的魅力值最大。

【输入格式】

　　第一行是三个整数：\(N,V\) 和 \(M\)，分别表示宝石的数量，小H能忍受的最大重量和能额外增加魅力值的宝石对数目。
　　接下来的 \(N\) 行，每行包含两个整数：\(w_i，p_i\)，分别表示第 \(i\) 块宝石的重量和能增加的魅力值。
　　再接下来的 \(M\) 行，每行包含三个整数：\(a_i,b_i\) 和 \(c_i\)，表示第 \(i\) 对宝石包含\(a_i、b_i\)两块宝石，选取这对宝石后能增加的额外魅力值为\(c_i\)。注意，\(M\)对宝石各不相同，即所有的 \(a_i，b_i\) 都互不相同。
　　同行相邻两个数据用一个空格分开。

【输出格式】

　　输出一个整数，表示按最多能增加的魅力值。

【输入输出样例1】

　Input

5 20 2
5 4
3 6
5 4
8 2
4 6
1 2 4
3 4 2

　Output

24

【样例1解释】

　　小H有 \(4\) 块宝石，他能忍受重量最大为 \(20\) 的手镯。有两对可增加额外魅力值的宝石对。你可以选择1和2这对宝石，然后再选取3和5这两块宝石，能增加总值为：4+6+4+4+6=24。可以证明这是唯一最优方案。

【数据限制】

　　对于 \(50\%\) 的数据，\(1≤N≤20\)，\(V≤1000\)
　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(V≤50000\)，\(M≤N/2\) 所有变量均在 int 范围内

【来源】

　　Mr.he