Aloha 是一个喜欢骑自行车的穷小子，但他太穷了，买不起自行车。

最近，Boom 的共享单车服务进入了他的学校。租用一次自行车仅需 $r$ 元。从那时起，Aloha 就可以租一辆自行车，享受骑行的速度与激情。

Boom 公司推出了一个名为“Boomsday Project”的促销计划。在该计划中，用户可以购买带有若干次免费租车机会和有效期的折扣卡。例如，购买一张带有 $k$ 次免费租车机会且有效期为 $d$ 天的折扣卡后，用户在接下来的 $d$ 天内，其后的 $k$ 次租车无需支付额外费用。注意，无论折扣卡是在第 $t$ 天的什么时候购买的，它总会在第 $t + d - 1$ 天结束时过期。此外，任何新购买的折扣卡都会覆盖之前的折扣卡，即使之前的折扣卡仍在有效期内；也就是说，当购买新折扣卡时，之前折扣卡剩余的免费租车次数会立即作废。

“Boomsday Project”共有 $n$ 种不同类型的折扣卡。第 $i$ 种类型的卡具有 $k_i$ 次免费租车机会，有效期为 $d_i$ 天，价格为 $c_i$ 元。每种类型的折扣卡都可以无限次购买。

给定租车记录，Aloha 想知道如果他采取最优策略，他最少需要支付多少钱。

输入格式

第一行包含三个整数 $n, m, r$ ($1 \le n \le 500, 1 \le m \le 10^5, 1 \le r \le 10^9$)，分别表示折扣卡的种类数、租车记录数以及单次租车的价格。

接下来 $n$ 行，指定 $n$ 种类型的折扣卡。第 $i$ 行包含三个整数 $d_i, k_i, c_i$ ($1 \le d_i, k_i, c_i \le 10^9$)，分别表示有效期、免费租车次数和折扣卡价格。

最后 $m$ 行描述 Aloha 的租车记录。第 $i$ 行包含两个整数 $p_i, q_i$ ($0 \le p_i \le 10^9, 0 \le q_i \le 3 \times 10^5, \sum_{i=1}^m q_i \le 3 \times 10^5$)，表示 Aloha 在第 $p_i$ 天会租车 $q_i$ 次。保证 $p_1, p_2, \dots, p_m$ 各不相同。

输出格式

输出一行一个整数，表示 Aloha 采取最优策略时所需支付的最小金额。

样例

样例输入 1

2 1 10
1 3 12
1 2 9
1 10

样例输出 1

42

样例输入 2

2 4 10
1 3 12
1 2 9
1 3
2 3
3 3
4 1

样例输出 2

45