P17431 [LBA-OI R5 A] 紫金断局

二十载紫金征途，每一分都是淬火的回响。

科比有 $n$ 场比赛记录，按时间顺序排列。第 $i$ 场得分为 $a_i$，且每场得分为正。他要将这些比赛分成至多 $k$ 段连续的时期，每段至少包含一场比赛。设最终分成 $t$ 段，第 $i$ 段的总得分为 $S_i$。 球迷写下 $m$ 条“曼巴法则”。每条法则给出三个整数 $x,y,p$： - 若 $p=0$，第 $x$ 段总分必须小于第 $y$ 段总分； - 若 $p=1$，第 $x$ 段总分必须大于第 $y$ 段总分。 若某条法则提到的 $x$ 或 $y$ 大于实际段数 $t$，该法则自动无效；否则必须满足。 一段时期的统治力是该段总得分的平方。求所有合法划分中，各段统治力之和的最大值。若不存在合法划分，输出 $-1$。

第一行三个整数 $n, k, m$。 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 场比赛的得分 $a_i$。 接下来 $m$ 行，每行三个整数 $x, y, p$，其中 $p \in \{0, 1\}$： - 若 $p = 0$，则法则为第 $x$ 时期的总得分 **小于** 第 $y$ 时期的总得分（即 $S_x < S_y$）； - 若 $p = 1$，则法则为第 $x$ 时期的总得分 **大于** 第 $y$ 时期的总得分（即 $S_x > S_y$）。

一行一个整数，表示最大统治力总和。若无解，输出 `-1`。

对于 $100\%$ 的数据，$1\le n,k\le 5\times 10^5$，$0\le m\le 5\times 10^5$，$0< a_i\le 10^9$。 ::cute-table{tuack} | 子任务编号 | $n$ | $k$ | $m$ | $a_i$ | 分值 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $\le 15$ | $\le 15$ | $\le 15$ | $\le 10^6$ | $25$ | | $2$ | 无特殊限制 | 无特殊限制 | $=0$ | 无特殊限制 | $25$ | | $3$ | ^ | $=1$ | 无特殊限制 | ^ | $25$ | | $4$ | ^ | 无特殊限制 | ^ | ^ | $25$ | **温馨提示：请注意答案的数量级。在 C++ 中可以使用 `__int128` 类型存储和运算 $2^{127}-1$ 级别的数字。你可以在主函数前加上以下内容来读入和输出 `__int128` 类型的变量：** ```cpp __int128 in() { __int128 k=0,f=1;char c=getchar(); while(c'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c