{"raw_statement":[{"iden":"statement","content":"Стив вошёл в трамвай и встал у окна: так он видел практически всех пассажиров. Пока он размышлял, кто же из них пригласил его на эту необычную встречу, сидящая поблизости пожилая женщина попросила помочь ей вытащить из трамвая её сумку на колёсиках: «Не сейчас, ещё несколько остановок ехать».\n\nСтив внимательно рассматривал всех, кто был в салоне трамвая. Вот пара девочек-школьниц, что-то оживлённо рассказывающих друг другу. Вот молодой человек, слушающий музыку и не особенно обращающий внимание на происходящее вокруг. Вот вполне серьёзный средних лет мужчина. Кстати, с небольшой папкой в руках. Может быть, он? Хотя вот тот студент с рюкзаком, который глаз не спускает со Стива, тоже вполне подходящий кандидат...\n\nСтив ехал уже достаточно долго, но к нему никто не подходил. Тот, кто позвал его на встречу, очевидно, знал, как Стив выглядит, а вот Стив не знал о незнакомце ничего. Стива охватило сильное желание выйти на следующей же остановке, и он направился к дверям. Пожилая дама тоже засобиралась на выход, и Стив помог ей вынести сумку. Поблагодарив, дама протянула ему карту памяти и сказала, что видела, как он обронил её в трамвае. Она ушла, а Стив остался на остановке.\n\nОтрезок пути, который Стив проехал на трамвае, можно разбить на n участков, каждый из которых ограничен двумя перекрёстками. Будем считать, что трамвай стартовал в момент времени t = 0 от перекрёстка #0. Участок от перекрёстка #(i - 1) до перекрёстка #i имеет длину ai. \n\nНа перекрёстке #i установлен двухсекционный светофор, на котором в течение ri секунд горит красный свет, а затем в течение gi секунд — зелёный свет. При этом известно, что di секунд назад на этом светофоре загорался зелёный свет. Время di отсчитывается от момента старта трамвая.\n\nТрамвай движется скоростью 1 единица расстояния в секунду, и что временем, которое он стоит на остановках, можно пренебречь. Считайте, что если трамвай подъехал к перекрёстку в момент, когда только что включился красный свет, проехать на зелёный он не успевает.\n\nСтив вышел на остановке, которая расположена сразу после последнего перекрёстка. Ваша задача — определить, сколько времени Стив ехал на трамвае.\n\nВ первой строке содержится целое число n (1 ≤ n ≤ 104) — количество перекрёстков, которые проехал Стив. \n\nВо второй строке содержатся целые числа a1, a2, ..., an (1 ≤ ai ≤ 104,  i = 1, 2, ..., n) — расстояния между перекрёстками.\n\nВ каждой из следующих n строк содержится по три целых числа ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 10000), описывающие очередной светофор.\n\nВ первой строке выведите единственное целое число — время, которое Стив потратил на поездку.\n\n"},{"iden":"входные данные","content":"В первой строке содержится целое число n (1 ≤ n ≤ 104) — количество перекрёстков, которые проехал Стив. Во второй строке содержатся целые числа a1, a2, ..., an (1 ≤ ai ≤ 104,  i = 1, 2, ..., n) — расстояния между перекрёстками.В каждой из следующих n строк содержится по три целых числа ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 10000), описывающие очередной светофор."},{"iden":"выходные данные","content":"В первой строке выведите единственное целое число — время, которое Стив потратил на поездку."},{"iden":"пример","content":"Входные данные3100 110 5080 20 5060 10 10030 40 50Выходные данные370"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of intersections.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of distances between consecutive intersections, where $ a_i $ is the length of segment $ i $.  \nFor each intersection $ i \\in \\{1, \\dots, n\\} $, let $ (r_i, g_i, d_i) \\in \\mathbb{Z}^3 $ denote the red duration, green duration, and offset of the traffic light: the green light turned on $ d_i $ seconds after departure.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^4 $  \n2. $ 1 \\leq a_i \\leq 10^4 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq r_i, g_i \\leq 1000 $, $ 1 \\leq d_i \\leq 10000 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute the total travel time $ T $, where the tram moves at 1 unit per second, and at each intersection $ i $, the tram must wait if it arrives during a red phase.\n\nThe traffic light cycle at intersection $ i $ has period $ c_i = r_i + g_i $, and at time $ t $, the light is green if and only if:  \n$$\n(t - d_i) \\bmod c_i < g_i\n$$\n\nLet $ t_0 = 0 $.  \nFor $ i = 1 $ to $ n $:  \n- Time to reach intersection $ i $: $ t_{i-1} + a_{i-1} $ (with $ a_0 = 0 $)  \n- Wait time at intersection $ i $:  \n  $$\n  w_i = \\begin{cases}\n  0 & \\text{if } (t_{i-1} - d_i) \\bmod c_i < g_i \\\\\n  c_i - \\left((t_{i-1} - d_i) \\bmod c_i - g_i\\right) & \\text{otherwise}\n  \\end{cases}\n  $$  \n  (i.e., wait until next green)  \n- $ t_i = t_{i-1} + a_{i-1} + w_i $\n\nTotal time: $ T = t_n + a_n $  \n\n**Output**  \n$ T $","simple_statement":"Steve took a tram ride with n intersections. Between each pair of consecutive intersections, the tram travels a distance of a_i units at 1 unit per second. At each intersection i, there is a traffic light with red time r_i, green time g_i, and it turned green d_i seconds before the tram started. If the tram arrives when the light is red, it must wait until it turns green. Calculate the total time Steve spent on the tram.","has_page_source":false}