Description

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.

Input Format

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.

Output Format

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.

2 2 10 5
1 1
2 2

14

Hint

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