P15554 [CCPC 2025 哈尔滨站] Many Many Sequence Covering Problems

考虑以下两个问题： $\textbf{Sequence Covering Problems}$： 在该问题中，初始会给出三个长度为 $n$ 的非负整数序列 $a,b,c$，每次可以用 $b_l+c_r$ 的代价选择区间 $[l,r]$，满足 $a_l,a_{l+1},\cdots,a_r$ 的最小值不为 $0$，将 $a_l,a_{l+1},\cdots,a_r$ 全部减去 $1$，目标是用最小的代价将 $a$ 中的所有数变为 $0$。 $\textbf{Many Sequence Covering Problems}$： 在 Sequence Covering Problems 的基础上，给出两个非负整数序列 $d,e$，现在可以做以下操作任意次：选择 $i\in[1,n]$，花费 $d_i$ 的代价让 $b_i$ 增大 $1$，或花费 $e_i$ 的代价让 $c_i$ 增大 $1$。在所有操作结束后，对操作后的 $b,c$ 序列求解其 Sequence Covering Problems，设其答案为 $P$，花费的代价为 $Q$，你需要最大化 $P-Q$ 的值，如果这个值可以是无限大，请输出 INF，否则请给出这个最大值。 现在你要解决 $\textbf{Many Many Sequence Covering Problems}$： 给出五个长度为 $n$ 的残缺序列 $A,B,C,D,E$，规定若 $A_i\ge 0$，则 $A_i$ 的值已经给出，否则认为 $A_i$ 的取值范围为 $[0,-A_i]$，对于 $B,C,D,E$ 序列同理。 你需要求出所有可能的情况下，其对应的 Many Sequence Covering Problems 的答案之和。由于答案可能是 INF，所以你需要分别给出，当答案不为 INF 时所有的答案之和，以及有多少种情况其对应的答案为 INF。由于答案可能很大，答案对 $998244353$ 取模。

输入第一行包含一个整数 $n$ ($1 \le n \le 5000$)，表示序列的长度。 输入第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$ ($0 \le |A_i| \le 5000$)。 输入第三行包含 $n$ 个整数 $B_1,B_2,\ldots,B_n$ ($0 \le |B_i| \le 5000$)。 输入第四行包含 $n$ 个整数 $C_1,C_2,\ldots,C_n$ ($0 \le |C_i| \le 5000$)。 输入第五行包含 $n$ 个整数 $D_1,D_2,\ldots,D_n$ ($0 \le |D_i| \le 5000$)。 输入第六行包含 $n$ 个整数 $E_1,E_2,\ldots,E_n$ ($0 \le |E_i| \le 5000$)。

输出只有一行，包含两个整数，分别表示当答案不为 INF 时，所有的答案之和对 $998244353$ 取模后的值，对应的答案为 INF 的情况数对 $998244353$ 取模后的值。