Dr. X 想从城市 出发前往城市 。对于所有满足 的整数 ，城市 与城市 之间都有高铁和飞机两种出行方式：
- 坐高铁从城市 到城市 花费的时间为 ；
- 坐飞机从城市 到城市 花费的时间为 。
然而，Dr. X 很害怕坐飞机，因此他希望整个行程中乘坐飞机的次数不得超过 次。
为了减少坐飞机的次数，Dr. X 可以选择从城市 直接飞到城市 ()，总飞行时间等于途经各段航线的飞行时间之和 \begin{aligned} f_i + f_{i+1} + \cdots + f_{i+j-1}, \end{aligned} 但这样一次连续飞行 只算乘坐一次飞机。请计算 Dr. X 从城市 出发到达城市 所需的最少时间。
