Có n căn nhà cần sơn. Căn nhà i được sơn bằng một trong 3 màu Xanh, Hồng, Vàng với mức giá tương ứng là a[i, 1], a[i, 2], a[i, 3].

Yêu cầu: Tìm cách sơn màu cho n ngôi nhà sao cho hai căn nhà cạnh nhau không được sơn cùng màu và tổng chi phí sơn là ít nhất.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n là số ngôi nhà;

• n dòng tiếp theo, dòng thứ i chứa ba số nguyên dương a[i, 1], a[i, 2], a[i, 3].

Dữ liệu ra:

Một số nguyên duy nhất là chi phí ít nhất để sơn n ngôi nhà.

Sample Input

4
13 23 12
77 36 64
44 89 76
31 78 45

Sample Output

137

Giải thích:

Các ngôi nhà lần lượt được sơn các màu: Vàng, Hồng, Xanh, Vàng. Tổng chi phí là: 12+36+44+45 = 137