Minimum Cost to Paint Offices

You are given n offices in a row. Each office can be painted in one of three colors: red, green, or blue. The cost of painting the i-th office in red, green, or blue is given by \(costs[i][0]\), \(costs[i][1]\), and \(costs[i][2]\) respectively.

Your task is to paint all offices such that no two adjacent offices share the same color, while minimizing the total painting cost. Formally, if \(c_i\) represents the color chosen for the \(i\)-th office, the condition \(c_i \neq c_{i+1}\) must hold for all \(1 \leq i < n\).

It is guaranteed that \(0 \leq n \leq 10^5\) and all costs are non-negative integers.

inputFormat

The first line contains a single integer n indicating the number of offices. If n = 0, no further input follows.

Each of the following n lines contains three space-separated non-negative integers, representing the cost to paint the corresponding office in red, green, and blue respectively.

Input Example:

3
17 2 17
16 16 5
14 3 19

outputFormat

Print a single integer, the minimum total cost required to paint all offices under the given constraints.

Output Example:

10

## sample

3
17 2 17
16 16 5
14 3 19

10