String theory

One of the most popular and (in many physicists' opinion) promising is a string theory. It states, that the multiverse is made of different dimensions but the highest is $11$-th dimension. Beyond $11$ dimensions, the universe would become unstable and dimensions higher than $11$ would collapse to an $11$-dimensional universe. You are now faced with the challenge in modelling String theoretical problem.

Our system has $n$ strings numbered from $1$ to $n$ placed at the lines $S$ = $i$ for $i$ = $1$, ..., $n$ on OTP Cartesian plane, where OT represent time frames and OS represent current string of the particle. Particles move only into the future and maybe jump between the strings expending the energy. Initially, particles only can stay in a rest without losing any energy, i.e. transition from state ($t$, $p$) to ($t$ + $1$, $p$) costs $0$ energy, and no other transitions are given within our system (yet). Note, our system does not possess backward time travelling (or assume that cost of transition back in time is infinity). Your main aim will be to calculate the minimum amount of energy particle require to travel from string s_1 at the time frame t_1 to the string s_2 at the time frame t_2, or say that this impossible to happen.

We now describe the certain external forces that may appear: teleports and massive objects. When teleport appear at time frame $t$ with energies costs (a_1, ..., a_{n-1}), it allows any particle at the state ($t$, $i$) to immediately jump to the state ($t$, $i$ + $1$) with energy loss a_i or to the state ($t$, $i$ - $1$) with energy loss a_{i-1} (whenever the string $i$ + $1$ or $i$ - $1$ exist). If we add massive object at time frame $t$ with energies (b_1, ..., b_n) it affect transition between time frames $t$ and $t$ + $1$ so that particle at string $i$ require to expend b_i energy to stay at the same string (otherwise particle just disappear in space-time). So there are $3$ type of requests you must fulfil:

- **1 t** a_1, ..., a_{n-1} - add teleport at time frame t with energies a_i; - **2 t** b_1, ..., b_n - add massive object at time frame $t$ with energies b_i; - **3** t_1 s_1 t_2 s_2 - we encountered a particle travelling between the states (t_1, s_1) $\to$ (t_2, s_2), what is minimal possible amount of energy expended by this particle?

Note, that if you are told to add $2$ teleports / massive objects in the same time frame, then later one replaces earlier one.