题目描述

你正在玩一个塔防游戏。游戏地图是一个 $M$ 行 $N$ 列的网格。

网格中的一些格子包含岩石，激光无法穿过这些岩石；一些格子包含敌人；其余格子为空。

你需要在一个空格子中放置一座激光塔。激光塔放置后，会向北、南、东、西四个方向发射激光。每束激光会一直前进，直到离开网格或遇到岩石为止；在路径上遇到的所有敌人都会被摧毁。

每个敌人都有一定分值。你的最终得分是所有被摧毁敌人的分值之和。

请计算能够获得的最大得分。

输入格式

第一行包含两个整数 $M,N$，分别表示网格的行数与列数。

第二行包含两个整数 $R,E$，分别表示岩石数量与敌人数量。

接下来 $R$ 行，每行包含两个整数 $l,c$，表示坐标为第 $l$ 行第 $c$ 列的格子中有一块岩石。

接下来 $E$ 行，每行包含三个整数 $l,c,s$，表示坐标为第 $l$ 行第 $c$ 列的格子中有一个敌人，摧毁它可以获得 $s$ 分。

输出格式

输出一个整数，表示在给定地图中可以获得的最大最终得分。

约束

• $1 \le M,N \le 10^9$。
• $1 \le R,E \le 100000$。
• 对所有坐标，$1 \le l \le M$，$1 \le c \le N$。
• 对所有敌人分值，$1 \le s \le 10000$。
• 每个格子至多包含一个敌人或一块岩石。
• 对于 $10\%$ 的测试，$M,N,R,E \le 1000$。
• 对于另外 $20\%$ 的测试，$R,E \le 1000$。
• 对于另外 $30\%$ 的测试，$R,E \le 30000$。

样例

输入

10 10
3 6
2 3
1 5
6 3
5 2 40
5 5 10
5 6 30
1 3 20
2 5 50
3 3 10

输出

90

样例解释

如果把激光塔放在坐标 $(5,3)$，可以得到：

分。

如果把激光塔放在坐标 $(5,5)$，本来可以得到更多分数，但该格子中有敌人，激光塔必须放在空格子上，因此不能选择该格子。