Színek kiválasztása
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Miss M nemcsak szeret érdekes történeteket kitalálni programozási problémákhoz, hanem imád festeni is, különösen a harmonikus színkombinációkat, mint például a színtárcsán található kiegészítő színeket. Azonban ezúttal másképp döntött a festményéhez való színek kiválasztásában.

Miss M $$$n$$$ színtárcsát vett elő, mindegyiken különböző árnyalatokkal, amelyek $$$(a_i+1)$$$ színből állnak, és már kiválasztott egy kezdőszínt minden tárcsán, megjelölve azt használtként. Ezután a következő algoritmust használva választja ki minden további színt:

  1. Keressük meg a leghosszabb sorozatot a megjelöletlen színek között az összes színtárcsán; ha több is van, válasszunk bármelyiket.
  2. Ha a sorozat hossza páratlan, vegyük a pontosan középső színt és jelöljük meg használtként.
  3. Ha a sorozat hossza páros, vegyük az egyik középső színt és jelöljük meg használtként.

Miss M további $$$m$$$ színt szeretne választani, és azt is szeretné tudni, hogy mi lesz a megjelöletlen színek sorozatának maximális hossza, mielőtt kiválasztja a $$$(m+n)$$$-edik színt.

Input

Az első sor két egész számot tartalmaz $$$n$$$ és $$$m$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq m \leq 10^{18}$$$) — a színtárcsák száma és a színek száma, amelyeket Miss M továbbiakban szeretne kiválasztani (azaz nem számítva az egyes tárcsákon az első megjelölt színeket).

A második sor $$$n$$$ egész számot tartalmaz $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$).

Garantált, hogy $$$m$$$ nem több, mint az összes $$$a_i$$$ összege.

Output

Írjunk ki egyetlen egész számot — a megjelöletlen színek sorozatának maximális hosszát, mielőtt Miss M kiválasztja az $$$(m+n)$$$-edik színt.

Scoring

Ha a megoldás helyesen működik $$$n=1$$$ és $$$a_1 \leq 100$$$ esetén, legalább $$$25$$$ pontot ér.

Ha a megoldás helyesen működik $$$n=1$$$ és $$$a_1 \leq 10^6$$$ esetén, legalább $$$50$$$ pontot ér.

Ha a megoldás helyesen működik $$$n=1$$$ esetén, legalább $$$75$$$ pontot ér.

Examples

Input
1 1
11
Output
11
Input
1 3
11
Output
5
Input
1 5
11
Output
2
Input
1 109
1033
Output
15
Input
3 1145
4034 5912 9134
Output
22

Note

Magyarázat a második példához: Egy színtárcsát adtak meg, amelyen $$$12$$$ szín található. Miss M már kiválasztott egy színt a tárcsáról (a képen az $$$1$$$-es számmal jelölve). Most további $$$3$$$ színt szeretne választani. Így a tevékenységek sorozata a következő:

  1. A megjelöletlen színek sorozatának maximális hossza $$$11$$$. Ezért kiválasztjuk a középső színt és jelöljük meg a $$$2$$$-es számmal.
  2. Most $$$5$$$ és $$$5$$$ megjelöletlen színből álló sorozatok vannak; választunk bármelyiket és a sorozat közepén kiválasztunk egy színt és jelöljük meg a $$$3$$$-as számmal.
  3. A sorozatok közül — $$$2$$$, $$$2$$$, és $$$5$$$ — választjuk az $$$5$$$-öt — ez a megjelöletlen színek sorozatának maximális hossza, mielőtt Miss M kiválasztja a $$$4$$$-edik színt.

A problémaállítás harmadik példájának színtárcsája.