Пункти
Джон — великий шанувальник парків розваг. Він відвідує їх кожні вихідні та грає в різноманітні ігри. Цього разу він натрапив на складну гру — стрільбу по мішенях. Мішені розташовані вздовж прямої лінії. Для кожної позиції мішені 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. Результат складається з максимальної кількості очок, які Джон може виграти, виведеної з початку рядка.