题目描述

一个人有n体力，m个金币，k个宝藏点，p条双向路径。

每个宝藏点都需要一定的金币v[i]才能挖掘获取价值w[i]。

每次通过一条路径都需要花费t的体力，可以走重复路径，但是宝藏只能获取一次。

你可以选择任意一个点作为起点，问最多能获得多少价值的宝藏。

输入描述

第一行输入4个整数，n, m, k, p。

接下来输入k行，每行两个整数，表示宝藏的价值w[i]和所需的金币v[i]。

接下来p行，每行输入三个整数u, v, t，表示u和v之间有一条需要花费t体力的路径。

1 <= n <= 10000；

1 <= m <= 10000；

1 <= k <= 20；

1 <= w[i], v[i], t <= 1000；

0 <= u, v <= k - 1；

1 <= p <= 19 * 19。

输出描述

输出一个整数，表示能获得的最大的宝藏价值。

输入示例

5 5 3 3
300 1
100 3
250 4
0 1 3
1 2 2
0 2 6

输出示例

550

提示信息

从0出发，收集0和1号点的宝藏。

时间限制：c/c++：1s；go/java：4s；其他语言：13s。