You are given an $m imes n$ integer matrix values representing the values of items in $m$ different shops, where each shop offers $n$ items. Each row values[i] is sorted in non increasing order.

Starting on day $d = 1$ and continuing until day $d = m imes n$, you purchase exactly one item per day. On day $d$, you can choose any shop with remaining items and purchase the last remaining item in that shop. The cost of purchasing an item of value $v$ on day $d$ is $v imes d$.

Return the maximum total spending possible to buy all $m imes n$ items.

Constraints:

• $1 \leq m ==$ values.length $\leq 10$

• $1 \leq n ==$ values[i].length $\leq 10^4$

• $1 \leq$ values[i][j] $\leq 10^6$

• values[i] is sorted in non increasing order.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.