You are given two integers, n and k, representing the total number of cities numbered from $0$ to n $- 1$, and the total number of days of a journey, respectively.

You are also given two $2 ext{D}$ integer arrays:

• stayScore of size k $ imes$ n, where stayScore[i][j] represents the points earned if you remain in city j on day i.

• travelScore of size n $ imes$ n, where travelScore[i][j] represents the points earned if you travel from city i to city j.

You may choose to start your journey in any city on day $0$.

On each day i from day $0$ to day k $- 1$, assuming your current location is city curr, you can perform exactly one of the following actions:

• Stay in city curr and earn stayScore[i][curr] points.

• Travel to any other city dest and earn travelScore[curr][dest] points, which updates your current location to city dest for the next day.

Return the maximum total points you can accumulate over the k days.

Constraints:

• $1 \leq$ n $\leq 200$

• $1 \leq$ k $\leq 200$

• n $==$ travelScore.length $==$ travelScore[i].length $==$ stayScore[i].length

• k $==$ stayScore.length

• $1 \leq$ stayScore[i][j] $\leq 100$

• $0 \leq$ travelScore[i][j] $\leq 100$

• travelScore[i][i] $== 0$

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.