Если девушка не идет к Денису, то Денис идет к девушке. Руководствуясь таким принципом, молодой человек вышел из дома, купил цветы и направился к Насте.

По пути от его дома до дома его возлюбленной есть дорога из $$$n$$$ полос, перейти которую за один зеленый свет не всегда возможно. Предвидя это, добрый мэр распорядился поставить в некоторых точках этой дороги островки безопасности. Каждый островок расположен после какой-то полосы, а также в начале и в конце дороги. На них пешеходы могут отдохнуть, набраться сил и дождаться зеленого света.

Денис подошел к левому краю дороги ровно в тот момент, когда загорелся зеленый свет. Мальчик знает, что светофор сначала горит $$$g$$$ секунд зеленым, а потом $$$r$$$ секунд красным, потом опять $$$g$$$ секунд зеленым и так далее.

Формально, дорогу можно представить как отрезок $$$[0, n]$$$. Изначально Денис стоит в точке $$$0$$$. Его задача - попасть в точку $$$n$$$ за минимальное возможное время.

Oн знает множество различных целых чисел $$$d_1, d_2, \ldots, d_m$$$, где $$$0 \leq d_i \leq n$$$  — координаты точек, в которых расположены островки безопасности. Только в одной из этих точек мальчик может находиться в момент, когда горит красный свет.

К сожалению, из-за волнения Денис не всегда может контролировать себя, поэтому сейчас на его передвижения наложены некоторые ограничения:

• Он обязан двигаться всегда, пока горит зеленый, ведь сложно стоять, когда тебя ждет такая девушка. Денис за $$$1$$$ секунду может изменить свое положение на $$$\pm 1$$$. При этом он должен всегда оставаться внутри отрезка $$$[0, n]$$$.
• Он может менять направление движения только на островках безопасности (ведь это безопасно). Это означает, что если за предыдущую секунду мальчик изменил свое положение на $$$+1$$$, то если он находится на островке безопасности, он может изменить свое положение на $$$\pm 1$$$, иначе он может изменить свое положение вновь только на $$$+1$$$. Аналогично, если за предыдущую секунду он изменил свое положение на $$$-1$$$, на островке безопасности он может изменить свое положение на $$$\pm 1$$$, а в любой другой точке вновь только на $$$-1$$$.
• В момент, когда загорается красный, мальчик должен оказаться на каком-то островке безопасности. Он сможет продолжить движение в любом направлении, когда вновь загорится зеленый.

Считается, что Денис перешел дорогу как только его координата станет равна $$$n$$$.

Эта задача оказалась не так проста, ведь возможно, таким способом даже невозможно перейти дорогу. Так как у Дениса все мысли о любви, он не справился решить ее и попросил нас помочь ему в этом. Найдите минимальное возможное время, за которое он сможет перейти дорогу по таким правилам, либо установите, что это сделать невозможно.