P15887 [ICPC 2026 NAC] Maki Conveyor Belt

Alice 和 Bob 正在一家回转寿司店用餐。（Maki 是一种寿司。）餐厅内的食客围绕着一个圆形传送带就座，传送带上有 $N$ 个位置，按顺时针顺序编号为 $1$ 到 $N$。Alice 坐在位置 $p_A$，Bob 坐在位置 $p_B$。 餐厅供应 $M$ 种不同类型的 Maki。传送带上共有 $K$ 个不同的盘子。第 $i$ 个盘子里装有 $x_i$ 个同一类型的 Maki，每个 Maki 的价格为 $c_i$ 枚硬币。同一种类型的 Maki 可能出现在多个盘子里，并且在不同盘子上价格可能不同。传送带上不会增加新的盘子，餐厅内也没有其他顾客（也许他们选了一家评分很低的 Maki 餐厅……）。 每个位置最多只有一个盘子。每秒钟，传送带顺时针旋转一格。形式化地说，如果位置 $N$ 上有一个盘子，它会移动到位置 $1$；其他所有盘子则从位置 $i$ 移动到位置 $i+1$。当一个盘子出现在食客面前时，他们可以立即从中抓取任意数量的 Maki，或者选择不抓取。例如，如果 Alice 面前有一个装有 $5$ 个 Maki 的盘子，她可以选择只拿 $2$ 个。食客可以在传送带首次旋转之前，就从面前的盘子中抓取 Maki。 Alice 和 Bob 想尽快回家观看他们最喜爱的寿司纪录片。他们知道餐厅的完整布局，并且每人希望吃到每种类型 Maki 的特定数量以满足需求。请帮助他们确定他们在餐厅所需的最短时间（以秒为单位），以及在该最短时间内满足需求所需的最小花费（以硬币为单位）。 :::align{center}  样例输入 1 中 Alice、Bob 以及盘子的初始位置。 :::

输入的第一行包含五个空格分隔的整数 $N$、$M$、$K$、$p_A$ 和 $p_B$，其中 $N$ $(2 \leq N \leq 10^{9})$ 是传送带位置的数量，$M$ $(1 \leq M \leq 10^{5})$ 是 Maki 种类的数量，$K$ $(1 \leq K \leq \min(2 \cdot 10^{5}, N))$ 是盘子的数量，$p_A$ 和 $p_B$ $(1 \leq p_A, p_B \leq N, p_A \not= p_B)$ 分别是 Alice 和 Bob 的座位位置。 第二行包含 $M$ 个空格分隔的整数 $a_i$ $(0 \leq a_i \leq 10^6)$，其中 $a_i$ 是 Alice 想要吃的第 $i$ 种 Maki 的数量。 第三行包含 $M$ 个空格分隔的整数 $b_i$ $(0 \leq b_i \leq 10^6)$，其中 $b_i$ 是 Bob 想要吃的第 $i$ 种 Maki 的数量。 接下来的 $K$ 行，每行描述一个盘子。第 $j$ 行包含四个空格分隔的整数 $s_j$、$t_j$、$x_j$ 和 $c_j$，其中 $s_j$ $(1 \leq s_j \leq N)$ 是盘子的起始位置，$t_j$ $(1 \leq t_j \leq M)$ 是盘子上 Maki 的种类，$x_j$ $(1 \leq x_j \leq 10^6)$ 是盘子上的 Maki 数量，$c_j$ $(1 \leq c_j \leq 10^6)$ 是每个 Maki 的价格。所有盘子的起始位置各不相同（即所有 $s_j$ 互不相同）。

输出两个整数：Alice 和 Bob 需要在餐厅停留的最短时间（以秒为单位），以及在该最短时间内满足需求所需的最小花费（以硬币为单位）。 如果无法使两人都得到满足，则输出 `impossible`。

翻译由 DeepSeek V3.2 完成