WPC4F  Through the troops
Having crossed the first hurdle, Mario encounters a long and narrow alleyway, with turtles. Mario can cross it by jumping from one turtle to another. Whenever Mario makes his jump on any given turtle, he can leave it in any of the three possible states, as per his choice. These states are:
 Active (A)
 Dormant (D)
 Bruised (B)
There are n turtles in the street, indexed 0..(n1). Each jump costs some amount of energy, which depends on the index of turtle as well as the state it is left in. However, Mario has to take care that no neighboring turtles are left in the same state, or otherwise they all will reunite and cause a fatal attack on Mario, as he is about to leave the alley.
The neighbors of turtle i are turtles i1 and i+1. (Edited: If n >= 3,) The first and last turtles are not neighbors.
You need to find out the minimum amount of energy required to cross the alley.
Input
first line contains no. of test cases T (T <= 5)
T input sets are given in the following manner:
 the first line contains n, no. of turtles (n <= 20)
 the next n lines have space separated 3 numbers (a1, a2, a3), the values of energy needed for ith turtle to change into states A D B (0 <= ai <= 1000)
 similarly, the inputs are given for other cases
Output
T lines, the minimal energy needed for each set of input
Example
Input: 2 3 0 1 2 1 4 8 9 2 5 4 10 10 10 2 4 9 12 7 10 6 6 6 Output: 4 25
hide comments
amulyagaur:
20171212 05:10:46
Recursion : 0.04s


rubenkresna22:
20170924 05:38:09
ac in 1000000000000000 gos 

nadstratosfer:
20170912 04:37:58
6 years on and the input is still malformed. Lame. 

surajmall:
20170804 08:16:52
good dp probem for beginners :P


nikhil2504:
20170726 19:20:14
Good for beginners like me. 

NIKHIL KUMAR SINGH:
20170108 17:13:34
So much of typing work.. Easy peasy.. AC in one go :) 

Harshwardhan Bansal:
20161001 13:04:51
New to DP...A very good problem to start... :) 

shubham9466:
20160906 20:53:34
Easy Dp!! Nice to start with :)


geeta:
20160704 14:59:09
green bar in one go!!! 

poojan :
20160509 07:39:58
easiest dp i ever solve!

Added by:  Walrus 
Date:  20111024 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Local Contest: WPC 4 