You are planning your vacation across $n$ cities labeled from $0$ to $n - 1$, over a total duration of $k$ weeks.

You are given a $2$D integer array flights of size $n imes n$, where flights[i][j] = 1 indicates that a direct flight exists from city i to city j, and flights[i][j] = 0 indicates no direct flight exists. You are also given a $2$D integer array days of size $n imes k$, where days[i][j] represents the maximum number of vacation days you can spend in city i during week j.

At the beginning of week $0$, you start in city $0$. On Monday of each week, you can either take a flight from your current city to another city if a direct flight exists, or remain in the current city. Flights take no significant time, and you can immediately enjoy vacation days in the chosen city for that week.

Return the maximum number of vacation days you can collect across all $k$ weeks.

Constraints:

• n == flights.length

• n == flights[i].length

• n == days.length

• k == days[i].length

• $1 \leq n, k \leq 100$

• flights[i][j] is either $0$ or $1$.

• $0 \leq$ days[i][j] $\leq 7$

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.