{"raw_statement":[{"iden":"background","content":"最近，小 Z 对冒泡排序产生了浓厚的兴趣。\n\n下面是冒泡排序的伪代码：\n\n```\n输入: 一个长度为 n 的序列 a[1...n]\n输出: a 从小到大排序后的结果\nfor i = 1 to n do:\n    for j = 1 to n - 1 do\n        if (a[j] > a[j + 1])\n            交换 a[j] 与 a[j + 1] 的值\n```\n\n冒泡排序的交换次数被定义为在排序时**进行交换的次数**，也就是上面冒泡排序伪代码**第六行**的执行次数。他希望找到一个交换次数尽量少的序列。"},{"iden":"statement","content":"小 Z 所研究的序列均由非负整数构成。它的长度为 $n$，且必须满足 $m$ 个附加条件。其中第 $i$ 个条件为：下标在 $[L_i, R_i]$ 中的数，即 $a_{L_i}, a_{L_{i+1}},\\dots,a_{R_i}$ 这些数，其最小值**恰好为 $\\boldsymbol{V_i}$**。\n\n他知道冒泡排序时常会超时。所以，他想要知道，在所有满足附加条件的序列中，进行冒泡排序的交换次数的最少值是多少。"},{"iden":"input","content":"本题有多组数据。\n\n输入的第一行包含一个正整数 $T$。\n\n对于每组数据，第一行包含两个正整数 $n,m$。数据保证 $1 \\leq n,m \\leq 10^6$。\n\n接下来 $m$ 行，每行三个非负整数 $L_i, R_i, V_i$，表示一组附加条件。数据保证 $1 \\leq L_i \\leq R_i \\leq n$、$0 \\leq V_i \\leq 10^9$。\n"},{"iden":"output","content":"输出共 $T$ 行，每行一个整数。\n\n对于每组数据，如果存在满足这 $m$ 个附加条件的序列，则输出在所有满足附加条件的序列中，冒泡排序交换次数的最小值。如果不存在满足所有条件的序列，则输出 $-1$。"},{"iden":"note","content":"**【样例解释 \\#1】**\n\n这组数据的约束条件为 $a_1 = 2022, \\min\\{a_2, a_3\\} = 39$。\n\n若 $a_2 = 39$，且 $39 \\leq a_3 < 2022$，则冒泡排序只有第一轮有交换操作，这一轮交换了 $a_1, a_2$ 和 $a_2, a_3$，总交换次数为 $2$。\n\n若 $a_2 = 39$，且 $a_3 \\geq 2022$，则冒泡排序只有第一轮有交换操作，这一轮仅仅交换 $a_1, a_2$，总交换次数为 $1$。\n\n若 $a_3 = 39$，且 $39 < a_2 < 2022$，则冒泡排序算法第一轮交换 $a_1, a_2$ 和 $a_2, a_3$，第二轮交换 $a_1, a_2$。总交换次数为 $3$。\n\n若 $a_3 = 39$，且 $a_2 \\geq 2022$，则冒泡排序算法第一轮交换 $a_2, a_3$，第二轮交换 $a_1, a_2$。总交换次数为 $2$。\n\n因此，交换次数的最小值为 $1$。\n\n----\n\n**【样例 \\#2】**\n\n见附件中的 `bubble/bubble2.in` 与 `bubble/bubble2.ans`。\n\n----\n\n**【样例 \\#3】**\n\n见附件中的 `bubble/bubble3.in` 与 `bubble/bubble3.ans`。\n\n这个样例满足测试点 $8 \\sim 10$ 的条件。\n\n----\n\n**【样例 \\#4】**\n\n见附件中的 `bubble/bubble4.in` 与 `bubble/bubble4.ans`。\n\n这个样例满足测试点 $13 \\sim 14$ 的条件。\n\n----\n\n**【样例 \\#5】**\n\n见附件中的 `bubble/bubble5.in` 与 `bubble/bubble5.ans`。\n\n这个样例满足测试点 $15 \\sim 16$ 的条件。\n\n----\n\n**【样例 \\#6】**\n\n见附件中的 `bubble/bubble6.in` 与 `bubble/bubble6.ans`。\n\n这个样例满足测试点 $23 \\sim 25$ 的条件。\n\n----\n\n**【数据范围】**\n\n本题共 $25$ 个测试点。全部测试点满足：$1 \\leq T \\leq 1000$，$1 \\leq \\sum n, \\sum m \\leq 10^6$，$1 \\leq L_i \\leq R_i \\leq n$，$0 \\leq V_i \\leq 10^9$。\n\n其中 $\\sum n, \\sum m$ 分别表示所有测试点的 $n$ 的总和和 $m$ 的总和。$\\sum n^2, \\sum m^2, \\sum n^3, \\sum m^3$ 的含义类似。\n\n| 测试点          | 数据范围                                                   | 特殊性质         |\n|:------------:|:------------------------------------------------------:|:------------:|\n| $1 \\sim 4$   | $n,m \\leq 7$，且最多 $2$ 组数据不满足 $n, m \\leq 5$              |              |\n| $5 \\sim 7$   | $n,m \\leq 17$，且最多 $3$ 组数据不满足 $n, m \\leq 9$             | A |\n| $8 \\sim 10$  | $n,m \\leq 100$，$\\sum n^3,\\sum m^3 \\leq 4 \\times 10^7$  | A |\n| $11 \\sim 12$ | $n,m \\leq 2000$，$\\sum n^2,\\sum m^2 \\leq 4 \\times 10^7$ | A |\n| $13 \\sim 14$ | $n,m \\leq 2000$，$\\sum n^2,\\sum m^2 \\leq 4 \\times 10^7$ | B |\n| $15 \\sim 16$ | $n,m \\leq 2000$，$\\sum n^2,\\sum m^2 \\leq 4 \\times 10^7$ | C |\n| $17 \\sim 18$ | $n,m \\leq 2000$，$\\sum n^2,\\sum m^2 \\leq 4 \\times 10^7$ |              |\n| $19$         | $\\sum n,\\sum m \\leq 10^6$                              | A |\n| $20$         | $\\sum n,\\sum m \\leq 10^6$                              | B |\n| $21 \\sim 22$ | $\\sum n,\\sum m \\leq 10^6$                              | C |\n| $23 \\sim 25$ | $\\sum n,\\sum m \\leq 10^6$                              |              |\n\n特殊性质 A：对于 $1 \\leq i \\leq m$，$0 \\leq V_i \\leq 1$。  \n特殊性质 B：对于 $1 \\leq i \\leq m$，$L_i = R_i$。  \n特殊性质 C：输入给出的 $m$ 个区间 $[L_i, R_i]$ 两两不相交。\n\n----\n\n**【提示】**\n\n本题的部分测试点输入量较大。我们建议你使用较为快速的读入方式。"}],"translated_statement":null,"sample_group":[["1\n3 2\n1 1 2022\n2 3 39\n","1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}