여권 도장의 추억

방금 새 여권을 받았다. 여권에는 출입국 심사관이 도장을 찍을 빈 페이지가 많다. 페이지가 너무 많아서 심사관들은 게을러서 페이지를 효율적으로 쓰지 않는다. 그래서 생각보다 빨리 새 여권이 필요할 수도 있다. 여행을 $k$번 계획해 두었다. 출입국 심사대를 지날 때마다 심사관은 도장이 없는 연속된 페이지를 찾아 그 페이지 전부에 도장을 찍는다. 심사관이 게을러서 어떤 연속된 페이지에 도장이 찍힐지는 정해져 있지 않다. 지금은 다음 여행에 필요한 만큼 연속된 빈 페이지가 없어서 새 여권을 신청하는 중이다. 신청하기 전에 여권을 넘기며 지난 여행을 떠올린다. 가장 싫었던 것은 심사관이 도장을 찍을 때까지 기다리는 시간이었다. 돌아보면 $k$번 여행했고, 도장이 찍힌 페이지는 $n$개의 연속된 구간을 이룬다. 각 심사관이 $0$쪽 이상 $s$쪽 이하의 페이지에 도장을 찍을 수 있고, 그 결과가 지금 여권에 있는 도장 구간과 정확히 같아지도록 하는 최소의 $s$를 구하라. 심사관마다 찍는 페이지 수는 달라도 되며, 0쪽을 찍는 것도 허용된다.

첫 줄에 두 정수 $n$ ($1 \le n \le 10^5$)과 $k$ ($n \le k \le 10^{18}$)가 주어진다. $n$은 도장이 찍힌 연속 구간의 개수이고, $k$는 여행 횟수이다. 다음 $n$개의 줄에는 각각 정수 $p$ ($1 \le p \le 10^{18}$)가 하나씩 주어진다. $p$는 한 구간에 있는 연속된 도장 페이지 수이다. 여권에 찍힌 도장 페이지는 모두 합쳐 최대 $10^{18}$이다.

각 심사관이 $0$ 이상 $s$ 이하의 페이지에 도장을 찍어 현재 여권의 도장 구간과 정확히 같아질 수 있는 최소의 정수 $s$를 한 개 출력한다.