U449055 海上升明月

月亮的微光穿过层云，露出皎洁与白皙。

海平面可以看作一个 $ n \times n $ 的方阵。 现在有 $ m $ 艘军舰，第 $ i $ 艘军舰的大小是 $ s_i $。 在 $ k $ 块地方，月光会使军舰暴露位置，敌人将会发起打击。 每块有月光的地方都会有一个明亮度，敌人会打击大小不小于这个明亮度且在这块位置上的最大军舰，**多艘军舰可以在同一个位置上**。 当然，如果没有超过这个明亮度的军舰，所有军舰都可以平安通过这块月光。 你可以同时操作一艘或者多艘军舰向右边或者下面走。 最开始，所有军舰都在 $ (1, 1) $ 上，到达 $ (n, n) $ 即视为退出海域。你的收益值为所有通过的军舰大小总和。最大化总收益。

第一行三个整数 $n, m, k$ 接下来 $ m $ 个整数，代表每个军舰的大小。 接下来 $ k $ 行，每行三个整数，分别代表月光的 $ x, y, l $，其中 $ l $ 代表明亮度。

一行一个整数，代表总收益的最大值。

在第一个例子中，所有军舰都能通过。 在第二个例子中，可以证明，没有一种方式可以将第四艘军舰带出海域。 对于 $100\%$ 的测试点，$ 1 \le n \le 1000$，$ 1 \le m \le 2\times10^5$，$ 1 \le k \le 2\times10^5$，$0 \le l \le 10^9$。