Minimum Cost Multi-Stage Route

Problem

Given two integer arrays stay and switch of length n, compute the minimum total cost to finish n stages. At each stage i, you must choose one of two modes: mode 0 or mode 1. If you stay in the same mode from stage i-1 to i, you pay stay[i]. If you switch modes between consecutive stages, you pay switch[i]. At stage 0, starting in either mode costs stay[0]. Return the minimum total cost over all valid mode choices.

Constraints

• 1 <= n <= 2 * 10^5
• stay.length == switch.length == n
• 0 <= stay[i], switch[i] <= 10^9
• The answer fits in a 64-bit signed integer