题目内容

在一条绵延的古商道上，分布着 $n$ 个可供设立货栈的地点。现在计划从中选取 $5$ 个地点作为接力货栈，将一批货物从最左侧传递至最右侧。货物在传递过程中会发生变化：若货物从货栈 $u$ 传递至货栈 $v$，则货物的数量会乘以 $\frac{c_u + c_v}{d}$，其中 $c_u, c_v$ 分别是两个货栈的转运效率系数，$d$ 是它们之间的距离。 已知第 $i$ 个候选地点的坐标为 $p_i$，转运效率系数为 $c_i$。坐标严格从左向右递增。规定最左侧地点（$i=1$）和最右侧地点（$i=n$）必须设立货栈，因此你还需要在剩余的 $n-2$ 个地点中选择恰好 $3$ 个地点建立货栈。货物从最左端出发时数量为 $1$，并且必须沿位置顺序依次经过这 $5$ 个货栈，即 $1 \to s_2 \to s_3 \to s_4 \to n$。 请你求出在所有选择方案中，最终到达最右侧时货物数量的最大值。

数据规模与约定：

• $5 \le n \le 2000$
• $1 \le p_i, c_i \le 10^4$，且 $p_1 < p_2 < \dots < p_n$

输入描述