Эта задача была скопирована автором с другой платформы. Codeforces категорически осуждает такое действие, поэтому дальнейшие посылки по этой задаче не будут приняты.
Debajyoti предстоит очень важная встреча, и он уже очень опаздывает. Harsh, его водитель, должен как можно быстрее доставить Debajyoti к месту встречи.
Harsh должен забрать Debajyoti из его дома и отвезите его к месту назначения, чтобы Debajyoti успел вовремя посетить встречу. Прямая дорога с \(n\) светофорами соединяет дом и место проведения интервью. Светофоры пронумерованы по порядку от \(1\) до \(n\).
Каждый светофор зацикливается через \(t\) секунд. \(i\)-й светофор горит \(\color{green}{\text{зелёным}}\) (в этом случае Harsh может проехать светофор) первые \(g_i\) секунд, и \(\color{red}{\text{красным}}\) (в этом случае Harsh должен дождаться включения \(\color{green}{\text{зелёного}}\)) оставшиеся \((t−g_i)\) секунд, после чего схема повторяется. Цикл каждого светофора повторяется бесконечно, и изначально, \(i\)-й светофор находится на секунде \(c_i\) в своём цикле (светофор с \(c_i=0\) только что включил \(\color{green}{\text{зелёный}}\)). В случае, если Harsh приближается к светофору в то же время, когда он меняет цвет, он будет подчиняться новому цвету. Формально, \(i\)-й светофор горит \(\color{green}{\text{зелёным}}\) в отрезок времени \([0,g_i)\) и \(\color{red}{\text{красным}}\) в отрезок времени \([g_i,t)\) (после чего цикл повторяется). \(i\)-й светофор изначально находится на \(c_i\)-й секунде своего цикла.
От \(i\)-го светофора ровно \(d_i\) секунд требуются, чтобы доехать до следующего светофора (то есть до \((i+1)\)-го светофора). Дом Debajyoti расположен прямо перед первым светофором, и Debajyoti попадает на интервью как только он проезжает \(n\)-й светофор. Другими словами, не требуется времени, чтобы доехать до первого светофора из дома Debajyoti или добраться до центра интервью от \(n\)-го светофора.
Harsh не знает, сколько времени потребуется Debajyoti, чтобы собраться. В ожидании он задается вопросом, какое минимально возможное количество времени ему может понадобиться провести за рулем, если он начнет движение в момент прибытия Debajyoti, которое может быть любым от \(0\) до \(\infty\) секунд от данного момента. Можете ли вы сказать Harsh минимально возможное количество времени, которое ему нужно провести в дороге?
Обратите внимание, что Harsh может начинать или останавливать движение только в целочисленные моменты времени.