You are given a two-dimensional array A of dimensions k n. The elements of the array are integer numbers. Your goal is to find the sum of the following sequence D = (d1, d2, ..., dn):

(a) di {A[1][i], A[2][i], ..., A[k][i]} for all 1 i n, i.e., di is some element in the array A at column i.

(b) Neighboring elements in D cant be from the same row in array A. For example, if di = A[x][i] for some x, then di1 6= A[x][i 1] and di+1 6= A[x][i + 1].

(c) The sum of all elements in D, i.e., d1 + d2 + ... + dn, is maximized. Your goal is to find the sum of the sequence D.

Provide a solution with O(nk) time and O(k) space complexity for full credit.