Background
Recently, little Z has developed a strong interest in bubble sorting.
Here is the pseudocode for bubble sort:
Input: a sequence a[1...n] of length n
Output: a result sorted from small to large
for i = 1 to n do:
for j = 1 to n - 1 do
if (a[j] > a[j + 1])
Swap the values of a[j] and a[j + 1]
The number of swaps in bubble sort is defined as the number of swaps performed during sorting, which is the number of times the sixth line of the above bubble sort pseudocode is executed. He wants to find a sequence with as few exchanges as possible.
Task Description
The sequences studied by little Z consists of non-negative integers. It is of length and must satisfy additional conditions.
The -th condition is: the minimum of the numbers with indices in , namely , is exactly .
He knows that bubble sort often times out. So, he wants to know what is the minimum number of swaps for bubble sort among all sequences that satisfy the additional condition.
Input Specification
There are multiple sets of data in this question.
The first line of input contains a positive integer .
For each set of data, the first row contains two positive integers n, m. Data guarantees .
The next m lines, each with three non-negative integers , represent a set of additional conditions. Data guarantees .
Output Specifiction
The output is lines in total, one integer per line.
For each set of data, if there are sequences that satisfy the m additional conditions, output the minimum number of exchanges in bubble sort among all the sequences that satisfy the additional conditions. If there is no sequence satisfying all conditions, output .
Sample Input 1
1
3 2
1 1 2022
2 3 39
Sample Output 1
1
Explanation for Sample Output 1
The constraints for this set of data are .
If , and , then the bubble sort has only the first round of swap operations. This round swaps and , and the total number of swaps is .
If , and , the bubble sort has only the first round of exchange operations, this round only exchanges , and the total number of exchanges is .
If , and , the bubble sort algorithm swaps and in the first round and in the second round. The total number of swaps is .
If , and , the bubble sort algorithm exchanges in the first round, and exchanges in the second round. The total number of swaps is .
Therefore, the minimum number of swaps is .
Additional Samples
Sample inputs and outputs can be found here.
- Sample 2 (
bubble2.in
andbubble2.ans
). - Sample 3 (
bubble3.in
andbubble3.ans
) corresponds to test cases 8-10. - Sample 4 (
bubble4.in
andbubble4.ans
) corresponds to test cases 13-14. - Sample 5 (
bubble5.in
andbubble5.ans
) corresponds to test cases 15-16. - Sample 6 (
bubble6.in
andbubble6.ans
) corresponds to test cases 23-25.
Constraints
There are 25 test cases in this question. All test points satisfy: , , , .
Case | Constraints | Special Property |
---|---|---|
1 - 4 | , all but 2 cases have | |
5 - 7 | , all but 3 cases have | A |
8 - 10 | , | |
11, 12 | , | |
13, 14 | B | |
15, 16 | C | |
17, 18 | ||
19 | A | |
20 | B | |
21, 22 | C | |
23, 24, 25 |
where represent the sum of and of all test points, respectively. meanings are similar.
- Special property A: For .
- Special property B: .
- Special property C: The input gives intervals Pairs do not intersect.
Hint
Some of the test points in this question have a large amount of input. We recommend that you use the fast I/O.
Comments