U106905整理书包

题目背景

随着学校学习压力的增大，CYX 的书包日益沉重，终于有一天，他受不了了，于是，他在整理了书包后，洛谷上又顺便多了一道题……

题目描述

他将他所需要的 n 样学习文具列了出来，第 i 样文具的重量是 w_i，价值是 v_i，减去包的自重，他最大只能承受 m 的重量，求他能装下的最大文具价值。

题出好了，但 CYX 很生气，因为这只是01背包的模板题，太简单了。于是他加了 k 种组合增益效果，每种组合效果用一个三元组(i,j,v) 表示，意思是如果同时选择了第 i 种文具和第 j 种文具，就能额外增加 v 的价值（注：组合之间不互斥，效果可以累加），还是求他能装下的最大价值。

难度是上来了，可不料 CYX 更生气了，因为，他不会做了……

输入格式

输入数据共 1+n+k 行。

第一行共三个整数 n，m，k*，分别表示 CYX 的学习文具的数量，除去书包的自重外 CYX 能承受的重量和增益组合的个数。

之后 n 行，每行两个整数 w_i 和 v_i，表示第 i* 种文具的重量和价值。

之后 k 行，每行三个整数 i，j，v，表示如果同时选择了第 i 种文具和第 j 种文具，就能额外增加 v* 的价值。

输出格式

仅一行一个整数，表示 CYX 能装下的最大价值。

输入输出样例

输入 #1

1
2
3
4
5
4 8 0
2 1
6 8
3 5
5 6

输出 #1

1
11

输入 #2

1
2
3
4
5
6
7
5 10 1
6 3
3 2
5 3
3 6
2 4
1 4 5

输出 #2

1
14

输入 #3

1
2
3
4
5
6
7
8
9
10
6 9 3
4 3
3 2
8 4
1 2
5 4
3 8
2 5 5
5 6 2
2 5 7

输出 #3

1
20

hint

【样例解释】

样例一解释：选择第 3，4个文具，价值和为 11。

样例二解释：选择第 1，4 个文具，满足第 1 种组合再加 5 的价值，价值和为 14。

样例三解释：选择第 2，4，5 个文具，满足第 1，3 种组合再加 12 的价值，价值和为 20。

【数据范围】

对于 10% 的数据，保证 1≤n≤20。

对于另外20% 的数据，保证 k*=0。

对于另外 30% 的数据，保证 1≤n≤100，1≤m≤200。

对于 100% 的数据，保证 1≤n≤10^3，1≤m≤2×10^3，0≤k≤10，1≤w**i≤300，1≤i,j≤n，1≤v≤500，1≤v**i≤500，i\=j*。

0 <= k <= 10 应该能想到枚举吧