Youve gotten into some trouble with the Santa Cruz locals and decided to make a run for it. You are on your hog (slang for motorcycle) trying to get from Santa Cruz to Achliopolis as fast as possible. Santa Cruz and Achliopolis are connected by two parallel roads, Highway A and Highway B. Along your way, A and B are connected at n junctions. At each junction you can exit from your current road and switch to the other. A may be a faster road between some junctions and B may be faster between others, but you will have to weight the gained speed against the time it takes to switch roads. Let ai denote the time it takes to get from the i-th junction to the (i + 1)-st junction on road A, and let bi denote the same for road B. Let k be the time it takes to switch roads at any junction. Come up with a dynamic programming algorithm that finds the fastest route from Santa Cruz to Achliopolis.

Need algorithm with running time and proof of correctness.