小 G 有一个 的网格条带和 种颜料，每种颜料在第 格内可用，涂一格需要花费 的代价。
现在，小 G 想在每一格内都涂上一种可用的颜料。小 G 希望这个网格条带内颜色尽量丰富，所以任意连续 格内的颜色不能全部相同。小 G 想知道，涂色的总代价最小是多少？如果不存在满足条件的染色方式，输出 .
第一行，三个整数 ，如题中所述。
接下来 行，每行三个整数 ，如题中所述。
一个整数，表示答案。
10 6 3 1 2 3 1 3 2 4 7 4 1 10 6 1 10 7 6 9 1
28
10 5 3 1 2 3 1 3 2 4 7 4 5 9 6 6 9 1
-1
【样例解释】
对于第一组数据，第 格分别涂第 种颜料，总代价为 ，可以证明这是满足条件的最小代价。
对于第二组数据，由于第 格没有颜料可用，因此不存在满足条件的染色方式，输出 。
【数据范围】
对于 的数据，，， ， 。
