P15887 [ICPC 2026 NAC] Maki Conveyor Belt

Alice and Bob are eating at a conveyor belt maki restaurant. (Maki is a kind of sushi). Diners in the restaurant sit around a circular conveyor belt with $N$ positions numbered from $1$ to $N$ in clockwise order. Alice sits at position $p_A$ and Bob sits at position $p_B$. The restaurant serves $M$ different kinds of maki. There are $K$ different plates set out on the conveyor belt. The $i^\text{th}$ plate consists of $x_i$ pieces of a single kind of maki and each piece costs $c_i$ coins. The same kind of maki may appear on multiple plates, and have different costs on different plates. No more plates will be added beyond what is already on the conveyor belt and no other customers are present at the restaurant (perhaps they picked a poorly rated maki restaurant$\ldots$). There is at most one plate per position. Every second, the conveyor belt rotates clockwise. Formally, if there is a plate at position $N$, it moves to position $1$; and all other plates move from position $i$ to position $i+1$. When a plate is in front of a diner, they may immediately grab any number of pieces from it, or choose not to grab any. For example, if there is a plate with $5$ pieces of maki in front of Alice, she can choose to only grab $2$. The diners may grab maki from plates in front of them before the belt first rotates. Alice and Bob want to return home as quickly as possible to watch their favorite sushi documentary. They know the full layout of the restaurant, and each have a desired number of pieces of each maki type they want to eat in order to be satisfied. Help them determine the minimum time (in seconds) they need to spend in the restaurant and the minimum cost (in coins) for them to become satisfied within that time. :::align{center}  Initial position of Alice, Bob, and the plates in Sample Input 1. :::

The first line of input contains five space-separated integers $N$, $M$, $K$, $p_A$, and $p_B$, where $N$ $(2 \leq N \leq 10^{9})$ is the number of conveyor belt positions, $M$ $(1 \leq M \leq 10^{5})$ is the number of maki types, $K$ $(1 \leq K \leq \min(2 \cdot 10^{5}, N))$ is the number of plates, and $p_A$ and $p_B$ $(1 \leq p_A, p_B \leq N, p_A \not= p_B)$ are Alice's and Bob's positions respectively. The second line contains $M$ space-separated integers $a_i$ $(0 \leq a_i \leq 10^6)$, where $a_i$ is the number of pieces of maki of type $i$ that Alice wants to eat. The third line contains $M$ space-separated integers $b_i$ $(0 \leq b_i \leq 10^6)$, where $b_i$ is the number of pieces of maki of type $i$ that Bob wants to eat. Each of the next $K$ lines describe a plate. The $j^\text{th}$ line contains four space-separated integers $s_j$, $t_j$, $x_j$, and $c_j$, where $s_j$ $(1 \leq s_j \leq N)$ is the starting position of the plate, $t_j$ $(1 \leq t_j \leq M)$ is the type of maki on the plate, $x_j$ $(1 \leq x_j \leq 10^6)$ is the number of pieces on the plate, and $c_j$ $(1 \leq c_j \leq 10^6)$ is the cost per piece. All plates have different starting positions (all $s_j$ are distinct).

Print two integers: the minimum time in seconds that Alice and Bob will need to spend in the restaurant and the minimum cost in coins for them to become satisfied within that minimum time. If it is impossible for both of them to ever be satisfied, print $\texttt{impossible}$.