Очки
Джон — большой любитель парков аттракционов. Каждые выходные он посещает их и играет в различные игры. В эти выходные он наткнулся на сложную игру — стрельбу по мишеням. Мишени расположены вдоль прямой линии. Для каждой позиции мишени i (предположим, что нумерация идет справа налево) есть три варианта количества очков, которые Джон может заработать, выбрав эту мишень: a_i, если не выбраны соседние мишени, b_i, если выбрана одна соседняя, и c_i, если выбраны две соседние. Можете ли вы помочь Джону выбрать мишени так, чтобы максимизировать количество очков, которые он может заработать?
Входные данные
Входные данные поступают из текстового файла. Сначала идет число n (n < 1000000) — количество мишеней. Затем следуют значения a_i, b_i и c_i для каждой мишени i. Программа должна вывести максимальное количество очков, которые Джон может заработать.
Входные данные корректны и заканчиваются концом файла.
Выходные данные
Программа должна вывести результат в стандартный вывод с начала строки.
Примечание: Примеры ввода/вывода приведены в таблице ниже. В первом тесте n=1, a_1=3, b_1=0, c_1=0, и максимальное количество очков равно 3. Во втором тесте n=1, a_1=1, b_1=2, c_1=3, и максимальное количество очков равно 1. Результат состоит из максимального количества очков, которые Джон может заработать, напечатанного с начала строки.