Програмчлалын олимпиадын бодлогын архив

Бөхийн өргөөнд болох концертын билетийг авахаар N тооны хүн дугаарлан зогсчээ. Хүн бүр нэг л билет авах зорилготой байгаа. Ганц л касс ажиллаж байсан тул хүмүүс хэд хэдээрээ нийлж билетээ бөөнөөр авах арга сэджээ. Ийм аргаар дараалан зогсч байгаа хэдэн хүн хоорондоо тохиролцоод хамгийн урдуур зогсч байгаа нэгэндээ бүх мөнгөө өгч хэдэн билет авахуулахаар шийдсэн байна.

Гэвч билет дамлагчидтай тэмцэхийн тулд касс нэг хүнд дээд тал нь гурван ширхэг билет л зарж байсан тул дараалан зогссон хоёр эсвэл гурван хүн л тохиролцож болохоор болжээ.

Кассчин дараалалд байгаа i-р хүнд нэг билет зарахдаа A_i хугацааг, хоёр билет зарахдаа B_i хугацааг, гурван билет зарахдаа C_i хугацаа зарцуулна. Дараалалд байгаа бүх хүнийг үйлчилж дуусах нийт хугацааны хамгийн бага утгыг олох програм бич.

Хоорондоо тохиролцсон хүмүүсийн хамгийн урд зогсч байгаа нь л билетүүдээ авна. Мөн хугацааг хэмнэхийн тулд илүү билет авахгүй (хэнд ч өгөхгүй билет авч болохгүй).

Input

Оролтын файлын эхний мөрөнд дараалалд байгаа хүний тоо болох N тоо өгөгдөнө (1 ≤ N ≤ 5000). Дараагийн N тооны мөр тус бүрд A_i, B_i болон C_i гэсэн натурал тоон гурвалууд байрлана. Эдгээр тоонууд тус бүр нь 3600-гаас хэтрэхгүй. Хүмүүсийг кассны талаас эхлэн дугаарлана.

Output

Гаралтын файлд, дараалалд байгаа бүх хүмүүст үйлчилж дуусахад шаардлагатай нийт хугацааны хамгийн бага утгыг секундээр илэрхийлсэн тоог бичнэ.

Example

Input:
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1

Output:
12
Input:
2
3 4 5
1 1 1
Output:
4