P1977 Taxi Carpooling

Once, little x went to a contest. Although the school was not far from the venue, little x still wanted to take a taxi. Taxis in the university town are a bit quirky: they do “carpooling.” That is, whether you ride alone or as a group, the total fare is the same per taxi ride (each taxi can seat at most $4$ passengers excluding the driver). Coincidentally, a group of OIers from the same school were gathered at the school gate that day, and everyone decisively decided to carpool to the venue. Here comes the problem: taxis kept passing by, but they were either full or had only one or two seats left. The OIers felt that getting on those would be a bad deal, and little x thought so too.

Suppose $N$ OIers plan to carpool. Time $0$ is the current moment. The fare from the school gate to the destination is $D$ yuan, charged per taxi ride regardless of how many OIers are inside. Assume the contest starts exactly at $S$ minutes, so any taxi that passes the gate after $S$ minutes can be ignored. You are given the arrival times $T_i$ and remaining seats $Z_i$ of all $K$ taxis that pass the gate within these $S$ minutes. For each taxi, the OIers may choose to let up to $Z_i$ people board (possibly $0$), or skip this taxi entirely. Time is money: each OIer’s waiting time in minutes at the gate is counted as spending the same amount of money. For example, if little x waits $20$ minutes, that means he spends an extra $20$ yuan. Under the requirement that all OIers can reach the venue before the contest starts, compute the minimum total amount of money they need to spend.

Each test case starts with four integers $N$, $K$, $D$, $S$, as described above. Then follow $K$ lines. The $i$-th line gives that the $i$-th taxi arrives at minute $T_i$, and its number of remaining seats is $Z_i$. Times are given in chronological order.

For each test case, output one line. If all of them can reach the venue before the contest starts, output a single integer representing the minimum amount of money (in yuan). Otherwise, output `impossible`.

Constraints: For $100\%$ of the testdata, $N, K, D, S \le 100$, $1 \le Z_i \le 4$, $1 \le T_i \le T_{i+1} \le S$. Translated by ChatGPT 5