有 $n$ 个元素，第 $i$ 个元素有五个参数 $x_i, a_i, b_i, c_i, d_i$。

你需要求出一个 $1 \sim n$ 的排列 $p$，满足 $p_1 = s, p_n = e$，同时最小化这个排列的权值。一个排列的权值定义为 $\sum_{i = 1}^{n - 1} f(p_i, p_{i + 1})$，其中

• 若 $i > j$，则 $f(i, j) = x_i - x_j + c_i + b_j$。
• 若 $i < j$，则 $f(i, j) = x_j - x_i + d_i + a_j$。

你只需要求出排列的最小权值即可。

数据范围：$1 \leq n \leq 5 \times 10^3$，$s \neq e$，$1 \leq x_1 < x_2 < \cdots < x_n \leq 10^9$，$1 \leq a_i, b_i, c_i, d_i \leq 10^9$。

时空限制：$4$s / $250$MiB。