Minimum House Restoration Cost

You are given n houses that need restoration. For each house, there are three types of restoration: Cosmetic, Structural, and Functional. The cost for each type is provided for every house.

You must choose one type for each house such that no two consecutive houses receive the same type of restoration. Your task is to determine the minimum total cost required to restore all houses following this rule.

Formally, if costs[i][0], costs[i][1], and costs[i][2] represent the costs for the 3 types of restoration for house i, and if we denote the chosen type for the i-th house as t(i), then the constraint is:

\( t(i) \neq t(i-1) \quad \text{for } 1 \le i < n \)

The objective is to minimize the sum:

\( \sum_{i=0}^{n-1} costs[i][t(i)] \)

where \( t(i) \in \{0,1,2\} \) corresponds to Cosmetic, Structural, and Functional, respectively.

inputFormat

The input is read from stdin and is formatted as follows:

1. Line 1: A single integer n representing the number of houses.
2. Next n lines: Each line contains 3 space-separated integers, representing the restoration costs for Cosmetic, Structural, and Functional restorations of a house.

outputFormat

Output a single integer to stdout: the minimum total restoration cost achievable under the constraint that no two adjacent houses use the same restoration type.

## sample

1
10 20 30

10

</p>