write a go solution for E2. Turtle and Inversions (Hard Version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is a hard version of this problem. The differences between the versions are the constraint on m and r_i<l_i+1 holds for each i from 1 to m-1 in the easy version. You can make hacks only if both versions of the problem are solved.Turtle gives you m intervals [l_1,r_1],[l_2,r_2],ldots,[l_m,r_m]. He thinks that a permutation p is interesting if there exists an integer k_i for every interval (l_i<=k_i<r_i), and if he lets a_i=maxlimits_j=l_i^k_ip_j,b_i=minlimits_j=k_i+1^r_ip_j for every integer i from 1 to m, the following condition holds:\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_iTurtle wants you to calculate the maximum number of inversions of all interesting permutations of length n, or tell him if there is no interesting permutation.An inversion of a permutation p is a pair of integers (i,j) (1<=i<j<=n) such that p_i>p_j.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^3). The description of the test cases follows.The first line of each test case contains two integers n,m (2<=n<=5*10^3,0<=m<=5*10^3) — the length of the permutation and the number of intervals.The i-th of the following m lines contains two integers l_i,r_i (1<=l_i<r_i<=n) — the i-th interval. Note that there may exist identical intervals (i.e., there may exist two different indices i,j such that l_i=l_j and r_i=r_j).It is guaranteed that the sum of n over all test cases does not exceed 5*10^3 and the sum of m over all test cases does not exceed 5*10^3.OutputFor each test case, if there is no interesting permutation, output a single integer -1.Otherwise, output a single integer — the maximum number of inversions.ExampleInput82 02 11 25 12 48 31 42 57 87 21 44 77 31 21 73 77 41 34 71 34 77 31 23 45 6Output1
0
8
18
-1
-1
15
15
NoteIn the third test case, the interesting permutation with the maximum number of inversions is [5,2,4,3,1].In the fourth test case, the interesting permutation with the maximum number of inversions is [4,3,8,7,6,2,1,5]. In this case, we can let [k_1,k_2,k_3]=[2,2,7].In the fifth and the sixth test case, it can be proven that there is no interesting permutation.In the seventh test case, the interesting permutation with the maximum number of inversions is [4,7,6,3,2,1,5]. In this case, we can let [k_1,k_2,k_3,k_4]=[1,6,1,6].In the eighth test case, the interesting permutation with the maximum number of inversions is [4,7,3,6,2,5,1].. Output only the code with no comments, explanation, or additional text.