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:
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.
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.
Í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.
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.
1 111
11
1 311
5
1 511
2
1 1091033
15
3 11454034 5912 9134
22
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ő: