Given :

Number of Visitors : N
Number of Gifts : K
Satisfaction Array : s[N][K], where s[i][j] denotes the visitor i's satisfaction when given gift j

Find the maximum satisfaction that can be achieved by hadning out exacly one gift to each visitor (in given order) such that no two adjacent visitors receive the same gift.