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 ≤ l ≤ r ≤ 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.

Input

First line contains two integers n and k (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ k ≤ min\{(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 ≤ a_i < b_i ≤ 10^9).

Output

Print one integer — the maximal sum of values Little D can get.

Examples

Input

2 1
1 3
2 4


Output

3

Input

3 3
1 4
5 7
3 6


Output

15

Note

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.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class IntervalOfIntervals3 {

	static int N;
	static long K;
	static long[] l, r;
	static ArrayList<Add> adds[];
	static final boolean debug = false;
	public static void main(String[] args) {
		FS in = new FS();
		N = in.nextInt();
		K = in.nextLong();
		l = new long[N];
		r = new long[N];
		for(int i = 0; i < N; i++) {
			l[i] = in.nextLong();
			r[i] = in.nextLong()-1;
		}
		
		adds = new ArrayList[N];
		for(int i = 0; i < N; i++) adds[i] = new ArrayList<Add>();
		TreeSet<Range> ranges = new TreeSet<Range>();
		// loop through r's
		for(int i = 0; i < N; i++) {
			// change the ranges in here
			long tookOver = 0;
			Range rr = new Range(r[i], r[i], -1);
			while(!ranges.isEmpty()) {
				Range f = ranges.floor(rr);
				if(f == null || f.r < l[i]) break;
				// intersect with this range
				long takeOver = -1;
				if(l[i] <= f.l && f.r <= r[i]) { //he's done for
					ranges.remove(f);
					takeOver = (f.r-f.l+1);
				}
				else if(f.l <= l[i] && r[i] <= f.r) { // he covers us
					//take care of left
					ranges.remove(f);
					takeOver = r[i]-l[i]+1;
					Range fl = new Range(f.l, l[i]-1, f.val);
					Range fr = new Range(r[i]+1, f.r, f.val);
					if(fl.l <= fl.r) ranges.add(fl);
					if(fr.l <= fr.r) ranges.add(fr);
				}
				else if(f.l < l[i]) { // he's on our left
					takeOver = f.r - l[i] + 1;
					f.r = l[i]-1;
				}
				else { // he's on our right
					takeOver = r[i] - f.l + 1;
					f.l = r[i] + 1;
				}
				if(takeOver > 0) adds[i].add(new Add(f.val+1, i, takeOver));
				tookOver += takeOver;
			}			
			ranges.add(new Range(l[i], r[i], i));			
			if(r[i]-l[i]+1-tookOver > 0) adds[i].add(new Add(0, i, r[i]-l[i]+1-tookOver));
		}	
		
		long lo = 1;
		long hi = 1_000_000_005L;
		long bestMinTake = 0; // highest thing such that >= K ranges above it
		while(lo <= hi) {
			long mid = (lo+hi)>>1;
			long v[] = go(mid);
			if(v[0] < K) hi = mid-1;
			else {
				if(mid > bestMinTake) bestMinTake = mid;
				lo = mid+1;
			}
		}
		long v2[] = go(bestMinTake+1);
		
		long res = v2[1];
		long need = K - v2[0];
		res += bestMinTake*need;
		
		System.out.println(res);
	}

	static long[] go(long minTake) {
		long totalSum = 0;
		long totalCnt = 0;
			
		long thisSubPrev[] = new long[N+1];
		int cl = 0;
		long curSum, curHave;
		curSum = curHave = r[0]-l[0]+1;
		thisSubPrev[1] -= curHave;
		
		for(int i = 1; i <= N; i++) {
			// Before we consider what's next, add answers if it works		
			if(curHave >= minTake) {
				totalCnt += cl+1;
				totalSum += curSum;
			}
			if(i == N) break;
			
			// process all the ADDS here
			for(Add a : adds[i]) {
				// currently taking range [0, cl], and for each k, range is [k, i-1]
				//update curHave (for cl)
				if(cl >= a.l && cl <= a.r) curHave += a.v;
				//update curSum [0, cl]
				long ll = Math.max(0, a.l);
				long rr = Math.min(cl, a.r);
				if(ll <= rr) curSum += (rr-ll+1)*a.v;
								
				//update diffs
				thisSubPrev[a.l] += a.v;
				thisSubPrev[a.r+1] -= a.v;
			}			
			//now move the ptr while we can
			while(cl < i && curHave + thisSubPrev[cl+1] >= minTake) {
				//shift ptr
				long nextVal = curHave + thisSubPrev[cl+1];
				curSum += nextVal;
				curHave = nextVal;
				cl++;
			}
			
		}		
		return new long[] {totalCnt, totalSum};
	}
	
	static class Range implements Comparable<Range>{
		long l, r;
		int val;
		public Range(long ll, long rr, int v) {
			l=ll;
			r=rr;
			val = v;
		}
		@Override
		public int compareTo(Range o) {
			if(l < o.l) return -1;
			else if(l > o.l) return 1;
			return 0;
		}
	}
	
	static class Add {
		int l, r;
		long v;
		public Add(int ll, int rr,long vv) {
			l=ll;
			r=rr;
			v=vv;
		}
		@Override
		public String toString() {
			return "[l="+l+" r="+r+" v="+v+"]";
		}
	}
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {br = new BufferedReader(new InputStreamReader(System.in));}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try { st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		long nextLong() { return Long.parseLong(next());}
	}

}
