时间限制： 1.0 秒

空间限制： 512 MB

题目描述

乔乔和牛牛去逛超市了，超市里有 $n$ 种商品，他们决定买一些商品回家。 但是，第 $i$ 种商品一旦被选择，购买的个数就必须是 $L_i$ 和 $R_i$ 之间的整数（含端点）。

某些商品之间有依赖关系，依赖关系有两种：

1. 只有第 $x$ 种商品被购买了，第 $y$ 种商品才可以被购买。
2. 只有第 $x$ 种商品被购买了，第 $y$ 种商品的购买个数才可以恰好是 $L_y$ 或 $R_y$。

购买一个商品的带来的开心程度和这个商品购买的个数有关，若第 $i$ 个商品购买了 $x_i$ 个 $(x_i>0)$，则收益为 $a_i x_i^2+b_i x_i+c_i$，否则为 $0$。

现在牛牛和乔乔想知道逛超市的最大总开心程度是多少，你能帮他们选购商品并确定购买商品数量吗？

输入格式

从标准输入读入数据。

第一行包含两个整数 $n,m$，表示商品数量和依赖关系数量。

接下来 $n$ 行，每行包含五个整数 $L_i,R_i,a_i,b_i,c_i$ ，描述一个商品。

接下来 $m$ 行，每行包含三个整数 $z,x,y$ ，表示第 $x$ 种商品对第 $y$ 种商品存在第 $z$ 种关系。

输出格式

输出到标准输出。

输出一个整数，表示最大总开心程度。

2 2
1 10 -2 3 -5
1 10 2 3 5
2 1 2
1 2 1

231

样例 1 解释

第 $1$ 种商品购买 $1$ 个，第 $2$ 种商品购买 $10$ 个。

子任务

对于所有数据，保证：

• $0\leq n \leq 10^4 , 0\leq m \leq 10^5$
• $1\leq L_i \leq R_i \leq 10^4 , -5\leq a\leq 5 , -10^4\leq b_i,c_i \leq 10^4, L_i+1 \leq R_i-1$
• $1\leq x,y \leq n,1\leq z\leq 2$

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。