Jerry 希望乘坐地铁从第 $1$ 站到达第 $n$ 站，地铁可以在一分钟内从第 $i$ 站到达第 $i+1$ 站。

他可以从 $n-1$ 张旅行卡中选择一张。第 $i$ 张旅行卡有范围 $r_i=i$ 和给定的价格 $p_i$。具体地，范围为 $r$ 的旅行卡允许从站点 $i$ 到达 $[i-r, i+r]$ 范围内的站点，否则需要进行换乘。从第 $i$ 站进行换乘需要花费 $d_i$ 分钟的时间，在起点站和终点站换乘不需要时间。一张旅行卡可以使用无数次，并且过程中只能使用同一张旅行卡。

Jerry 不是很富有，但是有一些空闲时间。他想要选择一张旅行卡，使得在 $t$ 分钟内可以到达终点的同时尽可能便宜。