B'Little D is a friend of Little C who loves intervals very much instead of number " 3 ". Now he has n intervals on the number axis, the i -th of which is [a_i,b_i] . Only the n intervals can not satisfy him. He defines the value of an interval of intervals [l,r] ( 1 <= q l <= q r <= q n , l and r are both integers) as the total length of the union of intervals from the l -th to the r -th. He wants to select exactly k different intervals of intervals such that the sum of their values is maximal. Please help him calculate the maximal sum. First line contains two integers n and k ( 1 <= q n <= q 3 cdot 10^5 , 1 <= q k <= q min { frac{n(n+1)}{2},10^9 } ) -- the number of intervals Little D has and the number of intervals of intervals he will select. Each of the next n lines contains two integers a_i and b_i , the i -th line of the n lines describing the i -th interval ( 1 <= q a_i < b_i <= q 10^9 ). Print one integer -- the maximal sum of values Little D can get. For the first example, Little D will select [1,2] , the union of the first interval and the second interval is [1,4] , whose length is 3 . For the second example, Little D will select [1,2] , [2,3] and [1,3] , the answer is 5+6+4=15 . '...