Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача J. И ещё несколько остановок

Задачу добавил: alef

Успешно сдано решений: 13

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

Стив вошёл в трамвай и встал у окна: так он видел практически всех пассажиров. Пока он размышлял, кто же из них пригласил его на эту необычную встречу, сидящая поблизости пожилая женщина попросила помочь ей вытащить из трамвая её сумку на колёсиках: «Не сейчас, ещё несколько остановок ехать».

Стив внимательно рассматривал всех, кто был в салоне трамвая. Вот пара девочек-школьниц, что-то оживлённо рассказывающих друг другу. Вот молодой человек, слушающий музыку и не особенно обращающий внимание на происходящее вокруг. Вот вполне серьёзный средних лет мужчина. Кстати, с небольшой папкой в руках. Может быть, он? Хотя вот тот студент с рюкзаком, который глаз не спускает со Стива, тоже вполне подходящий кандидат...

Стив ехал уже достаточно долго, но к нему никто не подходил. Тот, кто позвал его на встречу, очевидно, знал, как Стив выглядит, а вот Стив не знал о незнакомце ничего. Стива охватило сильное желание выйти на следующей же остановке, и он направился к дверям. Пожилая дама тоже засобиралась на выход, и Стив помог ей вынести сумку. Поблагодарив, дама протянула ему карту памяти и сказала, что видела, как он обронил её в трамвае. Она ушла, а Стив остался на остановке.

Отрезок пути, который Стив проехал на трамвае, можно разбить на 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), описывающие очередной светофор.

Выходные данные

В первой строке выведите единственное целое число — время, которое Стив потратил на поездку.

Пример

Входные данные
3
100 110 50
80 20 50
60 10 100
30 40 50
Выходные данные
370

Сдать задачу

Задать вопрос жюри по этой задаче