Отряд из $$$x$$$ клонов пробрался на корабль «Звезда смерти», чтобы помочь Люку Скайуокеру в битве с Дартом Вейдером. Корабль состоит из $$$n$$$ помещений и $$$m$$$ двунаправленных переходов между ними. Клоны оказались в помещении 1 и планируют пробраться в помещение $$$n$$$, где находится Люк.

Однако каждое помещение охраняется дроидами, $$$i$$$-е помещение охраняют $$$a_i$$$ дроидов. При появлении в помещении повстанцев происходит сражение. Если численность отряда клонов больше численности отряда дроидов, то все дроиды будут убиты, а клоны не понесут потерь. В противном случае клоны также уничтожат всех дроидов, но потеряют половину состава: если в момент начала сражения было $$$x$$$ клонов, то в конце останется $$$\left \lfloor \frac{x}{2} \right \rfloor$$$, округление вниз. Клонам придется сразиться с дроидами во всех помещениях, в которых они побывают, включая помещения 1 и $$$n$$$.

Помогите командиру отряда понять, какое максимальное количество клонов сможет добраться из помещения 1 до помещения $$$n$$$.