Google Apac 2017 : Problem D

Can anyone tell the approach for large dataset Google APAC Problem:D

i.e.

1 ≤ M ≤ 1,000,000,000.

8 ≤ N ≤ 12.

1 ≤ Ai,j ≤ 1,000,000,000.

1 ≤ Ci,j ≤ 1,000,000,000.

For small dataset it is a simple DP but no clue about large datasets .