Xallar#6176
John əyləncə parklarının böyük pərəstişkarıdır. O, hər həftə sonu parka gedir və müxtəlif oyunlar oynayır. Bu həftə sonu isə o, çətin bir oyunla qarşılaşıb - hədəf atıcılığı. Hədəflər düz bir xətt boyunca yerləşdirilib. Hədəflər sağdan sola doğru nömrələnib və hər bir hədəf üçün üç mümkün xal var: əgər qonşu hədəflər seçilməyibsə a_i, bir qonşu seçilibsə b_i, və iki qonşu seçilibsə c_i. John-un qazana biləcəyi xalları maksimuma çatdırmaq üçün ona hədəfləri seçməkdə kömək edə bilərsinizmi?
Proqramın girişi bir mətn faylından alınır. İlk sətirdə n (n < 1000000) - hədəflərin sayı verilir. Sonrakı sətirlərdə hər bir hədəf i üçün a_i, b_i və c_i dəyərləri verilir. Proqramın məqsədi John-un qazana biləcəyi maksimum xal sayını çap etməkdir.
Giriş məlumatları doğrudur və faylın sonu ilə bitir.
Proqram nəticəni standart çıxışa sətirin əvvəlindən çap etməlidir.
Qeyd: Giriş/çıxış nümunələri aşağıdakı cədvəldə göstərilib. İki test var. Hər biri yalnız bir hədəfdən ibarətdir. Birinci test üçün n=1, a_1=3, b_1=0, c_1=0 və maksimum xal sayı 3-dür. İkinci test üçün n=1, a_1=1, b_1=2, c_1=3 və maksimum xal sayı 1-dir. Nəticə, John-un qazana biləcəyi maksimum xal sayını göstərir və sətirin əvvəlindən çap edilir.
Nümunə 1