Max flight distance with limited energy

You are planning a trip over n days. dist[i] is how far you can fly on day i (a non-negative integer). You start with k units of energy, and k is also the most energy you can hold.

Each day you do exactly one of two things:

• Fly: spend 1 energy and cover dist[i]. You cannot fly with 0 energy.
• Rest: gain 1 energy, but never more than k.

Implement max_fly_distance(dist: list[int], k: int) -> int, which returns the largest total distance you can cover over the n days.

Constraints: 0 <= n <= 2000, 0 <= k <= 10^9, 0 <= dist[i] <= 10^6.

Example 1

dist = [4, 1, 7, 3], k = 1
output: 11

Fly on day 0 (4), rest on day 1, fly on day 2 (7), rest on day 3.

Example 2

dist = [1, 1, 10, 10, 10], k = 1
output: 21

Fly on day 0 (1), rest, fly (10), rest, fly (10). Resting on day 0 would gain nothing, because you are already at full energy.

A follow-up may ask you to return the day-by-day plan as well.