Бали#6176

Бали

0,5 секунди

256 мегабайтів

Дуже легка

Джон — великий шанувальник парків розваг. Він відвідує їх кожні вихідні та грає в різноманітні ігри. Цього разу він натрапив на складну гру — стрільбу по мішенях. Мішені розташовані вздовж прямої лінії. Для кожної позиції мішені $i$ (нумерація мішеней йде з права на ліво) існують три можливі кількості очок, які Джон може отримати, якщо обере цю мішень: $a_{i}$ a_i, якщо не вибрано сусідніх мішеней, $b_{i}$ b_i, якщо вибрано одну сусідню, і $c_{i}$ c_i, якщо вибрано дві сусідні. Чи можете ви допомогти Джону вибрати мішені так, щоб максимізувати кількість очок, які він може виграти?

Вхідні дані

Програма отримує вхідні дані з текстового файлу. Спочатку йде число $n$ ( $n < 1000000$ n < 1000000) — кількість мішеней. Далі йдуть значення $a_{i}$ a_i, $b_{i}$ b_i та $c_{i}$ c_i для кожної мішені $i$ . Програма повинна вивести максимальну кількість очок, які Джон може виграти.

Вхідні дані є коректними та завершуються кінцем файлу.

Вихідні дані

Програма виводить результат на стандартний вихід з початку рядка.

Приклади

Приклад 1

Примітка

Зразки вхідних/вихідних даних наведені в таблиці нижче. Є два тести. Кожен складається лише з однієї мішені. Для першого $n = 1$ n=1, $a_{1} = 3$ a_1=3, $b_{1} = 0$ b_1=0, $c_{1} = 0$ c_1=0, і максимальна кількість очок — $3$ . Для другого $n = 1$ n=1, $a_{1} = 1$ a_1=1, $b_{1} = 2$ b_1=2, $c_{1} = 3$ c_1=3, і максимальна кількість очок — $1$ . Результат складається з максимальної кількості очок, які Джон може виграти, виведеної з початку рядка.