I tried building solution by taking two matrices dpA[i][j] which tells me the count including the carriages from 1 to i of length k ending at A. Similarly I constructed dpB[i][j] (somewhat similar to 0-1 knapsack). But  of course this is wrong as my output will depend on the ordering of the carriages in input. Any suggestions if this approach can be corrected or need to think in completely different direction?

Thanks!