Weeks of Rest by Flight

A company lets an employee spend k weeks moving between n offices in different cities (numbered 0 to n - 1). On the Monday of the first week the employee is at office 0. The n × n matrix routes describes flights: routes[i][j] = 1 if there is a direct flight from city i to city j, otherwise 0 (no city has a flight to itself, and a return flight is not guaranteed). Flights are allowed only on Monday morning, at most one per Monday, or the employee can stay put. A flight takes no time. The n × k matrix rest says rest[i][w] is how many days the employee can rest in city i during week w. Rest counts toward the city where the week is spent (after a Monday flight, the whole week counts for the new city). The other days of the week are work days. Return the largest total number of rest days over the k weeks.

routes=[[0, 1, 0], [0, 0, 1], [1, 0, 0]], rest=[[2, 1, 0], [5, 0, 4], [0, 6, 7]] → 18

routes=[[0, 0], [0, 0]], rest=[[3, 2], [7, 7]] → 5