你在一家商店购物，商店总共出售 $M$ 件商品。商店的布局可以建模为一个二维平面，其中第 $i$ 件商品位于点 $(x_i, y_i)$，价格为 $p_i$。

商店提供 $N$ 种购物优惠。第 $i$ 种优惠由一个点 $(a_i, b_i)$ 指定，花费 $c_i$ 即可获得以下四个区域中你所选择的恰好一个区域内的每一件商品：

• 满足 $x \le a_i$ 且 $y \le b_i$ 的点 $(x, y)$ 区域。
• 满足 $x \le a_i$ 且 $y \ge b_i$ 的点 $(x, y)$ 区域。
• 满足 $x \ge a_i$ 且 $y \le b_i$ 的点 $(x, y)$ 区域。
• 满足 $x \ge a_i$ 且 $y \ge b_i$ 的点 $(x, y)$ 区域。

每种购物优惠最多只能使用一次。商品也可以通过支付各自的价格 $p_i$ 单独购买。

你想要获得商店中每一件商品至少各一个。求你必须支付的最低总成本。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$。

接下来的 $N$ 行，每行包含三个空格分隔的整数 $a_i, b_i$ 和 $c_i$ ($-10^9 \le a_i, b_i \le 10^9, 1 \le c_i \le 10^9$)。

接下来的 $M$ 行，每行包含三个空格分隔的整数 $x_i, y_i$ 和 $p_i$ ($-10^9 \le x_i, y_i \le 10^9, 1 \le p_i \le 10^9$)。

下表显示了 25 分的分布情况：

输出格式

在一行中输出你为了获得每一件商品至少各一个所必须支付的最低总成本。

样例

输入格式 1

2 4
1 1 3
3 3 13
0 0 2
0 2 5
2 0 4
2 2 3

输出格式 1

12

说明 1

使用第一种购物优惠，选择区域 $\{(x, y) \mid x \le 1, y \ge 1\}$ 以获得第二件商品。然后，单独购买第 1、3 和 4 件商品。总成本为 $3 + (2 + 4 + 3) = 12$。