ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / 9-р анги /

Нэгэн шинэ концертын анхны тоглолтыг үзэхээр N хүн тус бүр 1 билет худалдан авахаар кассанд дугаарлан зогсчээ. Зөвхөн нэг кассаар билет худалдаалж байсан нь маш удаан бөгөөд сүүлийн хүмүүс цөхөрч байв. Хэсэг хүмүүс билетийг худалдан авч байгаа хүн хэсэг билетийг бөөнд нь авахад 1 билет авахаас хурдан болохыг анзаарав. Иймд хүмүүс ярилцаад эхний хүндээ арынх нь хэсэг хүмүүс мөнгөө өгч билетээ захиалан авахаар тохиролцов. Билет худалдагч дамын наймаанаас сэргийлж 1 хүнд 3-аас илүүг худалдах боломжгүй ба зөвхөн зэргэлдээ байгаа 2 юмуу 3 хүн бие биенийхээ захиалгыг авч болно гэж мэдэгдэв. Дугаарт байгаа i-р хүн худалдаа хийхдээ 1 билет авахад A[i] секунд, 2 билет авахад B[i] секунд, 3 билет авахад C[i] секунд тус тус зарцуулах нь мэдэгдэж байв. Бүх худалдан авагчдад үйлчлэхэд зарцуулах хамгийн бага хугацааг ол.

Санамж : Хэсэг хүмүүсийн захиалгыг зөвхөн эхнй хүн нь л гүйцэтгэнэ. Мөн дамлах зорилгоор илүү билет авахыг хориглоно.

Input

Эхний мөрөнд дугаарлан зогсоо хүмүүсийн тоо N өгөгдөнө. ( 1<=N<=5000 )

Дараагийн N мөр бүрт A[i], B[i], C[i] 3 натурал тоонууд өгөгдөнө. Тоо бүр нь 3600-гаас хэтрэхгүй.

Дугаарлан зогсоо хүмүүс касс талаасаа дугаарлагдана.

Output

Бүх худалдан авагчдад үйлчилж дуусах хамгийн бага хугацаа.

Example

Input:
5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

Output:
12

Input 2:

2

3 4 5

1 1 1

Output 2:

4