Alex likes to play with one and zero as you know .

But Alex does’t have a girlfriend now because his girlfriend is trapped in Alcatraz Island.So Alex wants to rescue her.Now Alex has some information about this place.there are two coast(海岸线) which parallel to each otherand there some castles(城堡) in each cosat.Each coast have n(n<=15) castles,each castle has a id which begins from 1.Each castle just has a undirected road with it's adjacent castle .What's more,He must build exactly k bridges between two coast,and the bridge can only be built between two castles which have the same id and the cost is zero.Now Alex is in the first castle in the first coast and his girlfriend is in the last castle in the second coast ,please calculate the shortest distance Alex needs to walk.

First are two integers n (n<=15) and k (1 <= k<=n);
Next contains two lines ,every line contains n-1 integers
which represent the distance between two adjacent castles and the value is less than 100.

For each case output the answer represent shortest distance Alex needs to walk.