F. Светофоры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Начался новый учебный год, а значит опять придется ехать в автобусе по пробкам в университет.

Вы знаете, что между начальной и конечной остановками расположено n перекрестков со светофорами.

Сама начальная остановка находится сразу после перекрёстка 0, а конечная — сразу за перекрестком n.

Вы знаете, что от (i - 1)-го до i-го перекрестка автобус доезжает за ai секунд. Временем на остановках можно пренебречь.

Про светофор на i-м перекрестке известны три характеристики:

  • ri — сколько секунд на светофоре горит красный свет;
  • gi — сколько секунд горит зеленый свет;
  • di — за сколько секунд до вашей посадки в автобус на светофоре загорался зеленый свет.

Если автобус подъезжает ровно в тот момент, когда свет как раз переключается на красный свет — автобус уже не проедет.

Используя всю эту информацию, определите — сколько секунд займет вся поездка на автобусе от начала до конца.

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

В первой строке содержится целое число n (1 ≤ n ≤ 104) — количество перекрёстков у вас на пути.

Во второй строке содержатся целые числа a1, a2, ..., an (1 ≤ ai ≤ 104,  i = 1, 2, ..., n) — время, за которое автобус проезжает путь от (i - 1)-го до i-го перекрёстка.

В каждой из следующих n строк содержится по три целых числа ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 104) — характеристики i-го светофора.

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

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

Пример
Входные данные
3
100 110 50
80 20 50
60 10 100
30 40 50
Выходные данные
370
Примечание

Первый тестовый пример

  • До 1-го светофора доехали за 100 секунд.
  • 1-й светофор горит зеленым в моменты времени [ - 50; - 30], [50;70]; [150;170];
  • Вы приехали во время красного света светофора, соответственно автобус будет ждать до 150 секунд.
  • До 2-го светофора автобус доедет за 110 секунд — уже прошло 150 + 110 = 260 секунд.
  • 2-й светофор горит зеленым в моменты времени [ - 100; - 90], ... [180;190]; [250;260]; [320;330].
  • Автобус приехал ровно в начале красного света светофора, соответственно придется ждать до 320 секунд.
  • До 3-го светофора автобус доедет за 50 секунд — уже прошло 320 + 50 = 370 секунд.
  • 3-й светофор горит зеленым в моменты времени [ - 50; - 10], ... [300;340]; [370;410].
  • Автобус приехал ровно в начале зеленого света светофора, поэтому он сразу проехал перекрёсток без ожидания.
  • Итого вы проехали весь путь за 370 секунд.