Если девушка не идет к Денису, то Денис идет к девушке. Руководствуясь таким принципом, молодой человек вышел из дома, купил цветы и направился к Насте.
По пути от его дома до дома его возлюбленной есть дорога из \(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\).
Эта задача оказалась не так проста, ведь возможно, таким способом даже невозможно перейти дорогу. Так как у Дениса все мысли о любви, он не справился решить ее и попросил нас помочь ему в этом. Найдите минимальное возможное время, за которое он сможет перейти дорогу по таким правилам, либо установите, что это сделать невозможно.