Тарогийн зуны амралт маргааш эхлэх гэж байгаа тул тэр одоо төлөвлөгөө гаргахаар шийджээ.

Амралт нь N өдөр үргэлжилнэ. Өдөр бүр (1 ≤ i ≤ N), Таро дараах 3 үйл ажиллагаанаас зөвхөн нэгийг сонгон хийж чадна:

• A: Далайд сэлэх → aᵢ оноо аз жаргал нэмэгдэнэ
• B: Ууланд шавж барих → bᵢ оноо аз жаргал нэмэгдэнэ
• C: Гэртээ хичээл хийх → cᵢ оноо аз жаргал нэмэгдэнэ

⚠️ Анхаарах зүйл: Таро амархан уйддаг тул хоёр дараалсан өдөр ижил үйл ажиллагаа хийж болохгүй.

Зорилго

• Тарогийн авч болох хамгийн их аз жаргалын нийлбэр оноог ол.

Оролтын файлын формат:

Дараах хэлбэрээр стандарт оролтоос өгөгдөнө:

N
a₁ b₁ c₁
a₂ b₂ c₂
...
aₙ bₙ cₙ
​

Гаралтын файлын формат

• Тарогийн авч болох хамгийн их аз жаргалын нийлбэр-ийг хэвлэ.

Хязгаарлалтууд

• Бүх оролт нь бүхэл тоо
• 1 ≤ N ≤ 100000
• 1 ≤ aᵢ, bᵢ, cᵢ ≤ 10000

Дэд бодлого

Жишээ тест

Оролот - 1

3
10 40 70
20 50 80
30 60 90

Гаралт - 1

210

Оролот - 2

1
100 10 1

Гаралт - 2

100

Оролот - 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Гаралт - 3

46

Тайлбар:

Таро дараах дарааллаар хийвэл:

C → A → B → A → C → B → A