P11290 【MX-S6-T2】「KDOI-11」飞船

原题链接：。

巡造了一个很牛的飞船，巡为了测试她的飞船，造了一条无限远的从起点出发的射线作为跑道。在跑道上有 $n$ 个加油站，第 $i$ 个在距离起点 $p_i$ 的位置，巡可以在这里花费 $t_i$ 的时间加编号为 $x_i$ 的燃油，**同一个加油站的油不能加两次**，**保证 $\boldsymbol{1\leq x_i\leq 4}$ 且 $\boldsymbol{x_i}$ 为整数**。 巡的飞船牛在两个点： - 这个飞船油量消耗极低，在本题中可以忽略不计。也就是，**我们不考虑油消耗殆尽的情况。** - 如果给飞船加编号为 $x$ 的燃油，**飞船的速度会从 $v$ 提升为 $v\times x$**。需要注意的是，**燃油的效果能叠加**。 现在，巡给出了 $q$ 次询问。每次巡会将终点设在跑道上距离起点 $y_i$ 的位置，从起点出发，将飞船速度设定为 $1$ 单位每时间，途径的每个加油站可以自由选择是否加油。你需要告诉巡每次至少需要多少时间才能到达终点（即 $y_i$）。

无

无

**【样例解释 #1】** - 对询问 $y_1=1$，不加油，需要时间为 $1$。 - 对询问 $y_2=4$，不加油，需要时间为 $4$。 - 对询问 $y_3=10$，在位于起点 $3$ 单位距离的加油站 $2$ 加 $2$ 号燃油，速度提升为 $2$，需要时间为 $3+1+\frac{10-3}{2}=7.5$。 **【样例 #2】** 见附件中的 `ship/ship2.in` 与 `ship/ship2.ans`。 该组样例满足测试点 $1\sim 3$ 的约束条件。 **【样例 #3】** 见附件中的 `ship/ship3.in` 与 `ship/ship3.ans`。 该组样例满足测试点 $5\sim 7$ 的约束条件。 **【样例 #4】** 见附件中的 `ship/ship4.in` 与 `ship/ship4.ans`。 该组样例满足测试点 $18\sim 20$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证：$1\leq n\leq 10^5$，$1\leq q\leq10^5$，$1\leq p_1