Стив вошёл в трамвай и встал у окна: так он видел практически всех пассажиров. Пока он размышлял, кто же из них пригласил его на эту необычную встречу, сидящая поблизости пожилая женщина попросила помочь ей вытащить из трамвая её сумку на колёсиках: «Не сейчас, ещё несколько остановок ехать».
Стив внимательно рассматривал всех, кто был в салоне трамвая. Вот пара девочек-школьниц, что-то оживлённо рассказывающих друг другу. Вот молодой человек, слушающий музыку и не особенно обращающий внимание на происходящее вокруг. Вот вполне серьёзный средних лет мужчина. Кстати, с небольшой папкой в руках. Может быть, он? Хотя вот тот студент с рюкзаком, который глаз не спускает со Стива, тоже вполне подходящий кандидат...
Стив ехал уже достаточно долго, но к нему никто не подходил. Тот, кто позвал его на встречу, очевидно, знал, как Стив выглядит, а вот Стив не знал о незнакомце ничего. Стива охватило сильное желание выйти на следующей же остановке, и он направился к дверям. Пожилая дама тоже засобиралась на выход, и Стив помог ей вынести сумку. Поблагодарив, дама протянула ему карту памяти и сказала, что видела, как он обронил её в трамвае. Она ушла, а Стив остался на остановке.
Отрезок пути, который Стив проехал на трамвае, можно разбить на n участков, каждый из которых ограничен двумя перекрёстками. Будем считать, что трамвай стартовал в момент времени t = 0 от перекрёстка #0. Участок от перекрёстка #(i - 1) до перекрёстка #i имеет длину ai.
На перекрёстке #i установлен двухсекционный светофор, на котором в течение ri секунд горит красный свет, а затем в течение gi секунд — зелёный свет. При этом известно, что di секунд назад на этом светофоре загорался зелёный свет. Время di отсчитывается от момента старта трамвая.
Трамвай движется скоростью 1 единица расстояния в секунду, и что временем, которое он стоит на остановках, можно пренебречь. Считайте, что если трамвай подъехал к перекрёстку в момент, когда только что включился красный свет, проехать на зелёный он не успевает.
Стив вышел на остановке, которая расположена сразу после последнего перекрёстка. Ваша задача — определить, сколько времени Стив ехал на трамвае.
В первой строке содержится целое число 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), описывающие очередной светофор.
В первой строке выведите единственное целое число — время, которое Стив потратил на поездку.
## Входные Данные
В первой строке содержится целое число 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), описывающие очередной светофор.
## Выходные Данные
В первой строке выведите единственное целое число — время, которое Стив потратил на поездку.
## Пример
Входные данные3100 110 5080 20 5060 10 10030 40 50Выходные данные370
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of intersections.
Let $ 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 $.
For 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.
**Constraints**
1. $ 1 \leq n \leq 10^4 $
2. $ 1 \leq a_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq r_i, g_i \leq 1000 $, $ 1 \leq d_i \leq 10000 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute 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.
The 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:
$$
(t - d_i) \bmod c_i < g_i
$$
Let $ t_0 = 0 $.
For $ i = 1 $ to $ n $:
- Time to reach intersection $ i $: $ t_{i-1} + a_{i-1} $ (with $ a_0 = 0 $)
- Wait time at intersection $ i $:
$$
w_i = \begin{cases}
0 & \text{if } (t_{i-1} - d_i) \bmod c_i < g_i \\
c_i - \left((t_{i-1} - d_i) \bmod c_i - g_i\right) & \text{otherwise}
\end{cases}
$$
(i.e., wait until next green)
- $ t_i = t_{i-1} + a_{i-1} + w_i $
Total time: $ T = t_n + a_n $
**Output**
$ T $