Design a dynamic programming algorithm to solve the following problem: Input: A $2\backslash$times n array A of positive integers, and an integer $0<=$ k $<=$ n$.$

Output: The value of the maximum valued path through the array, which passes through exactly $2$n $$ k cells $($cells cannot be repeated$).$ The value of such a path is the sum of the values of the cells it passes through. Cells are adjacent to its orthogonal neighbours, but not its diagonal neighbours. Such a path must begin in the first column $($i$.$e$.$ A$[$i$,1]$ for some i $=1,2)$ and end in the last column.

Your algorithm$$s runtime must be O$($nk$).$