구간 나누기

수직선 위에 양의 정수 끝점을 갖는 $N$개의 구간 $[L_1, R_1], \ldots, [L_N, R_N]$이 주어진다. 나누기 연산은 구간 $[L, R]$을 두 구간 $[L, M]$과 $[M, R]$로 바꾼다. 이때 $M$은 양의 정수이고 $L < M < R$이다. 처음 주어진 구간뿐 아니라 앞선 나누기 연산으로 만들어진 구간도 나눌 수 있다.

양의 정수 $A < B$에 대해, 구간 $[A, B]$가 구간 $[L, R]$의 길이의 절반 이상을 덮으면 $[A, B]$는 $[L, R]$을 강하게 덮는다고 한다.

주어진 $N$개의 구간에 $K$번의 나누기 연산을 적용해 얻은 $N + K$개의 구간 모두를 구간 $[A, B]$가 강하게 덮을 때, 그러한 $[A, B]$의 길이의 최솟값을 구하라.

첫 줄에 정수 $N$과 $K$가 주어진다 ($1 \le N \le 10^5$, $0 \le K \le 10^{14}$). 다음 $N$개 줄의 $i$번째 줄에는 $i$번째 구간의 왼쪽 끝점 $L_i$와 오른쪽 끝점 $R_i$가 주어진다 ($1 \le L_i < R_i \le 10^9$). 주어진 구간에 $K$번의 나누기 연산을 적용할 수 있다고 가정해도 된다. 주어진 구간 중 일부는 서로 같을 수 있다.

강하게 덮는 조건을 만족하는 구간 $[A, B]$의 길이의 최솟값을 정수 하나로 출력한다.