Memories of Passport Stamps

You just got a new passport with many blank pages for immigration officers to stamp. Because it has so many pages, the officers are too lazy to use them efficiently, so you may need a new passport sooner than you expect. You planned $k$ trips. At each passport control, the officer finds some contiguous pages with no stamps and stamps all of them. Which contiguous pages get stamped is not fixed, since the officers are lazy. Now there are not enough contiguous blank pages for your next trip, so you are applying for a new passport. Before that, you leaf through the passport and recall your trips. What you disliked most was waiting for the officers to stamp it. Looking back, you took $k$ trips, and the stamped pages form $n$ contiguous sections. Find the minimum value $s$ such that each officer can stamp between $0$ and $s$ pages (inclusive), so that the stamped sections are exactly the ones in your passport now. Different officers may stamp different numbers of pages, and an officer may stamp zero pages.

The first line contains two integers $n$ ($1 \le n \le 10^5$) and $k$ ($n \le k \le 10^{18}$), where $n$ is the number of contiguous stamped sections and $k$ is the number of trips. Each of the next $n$ lines contains one integer $p$ ($1 \le p \le 10^{18}$), the number of contiguous stamped pages in one section. The passport has at most $10^{18}$ stamped pages in total.

Output a single integer, the minimum value $s$ such that each officer can stamp between $0$ and $s$ pages, inclusive, so that the stamped sections are exactly the ones in your passport now.