P7425 [THUPC 2017] Airport

An airport has $a+b$ parking stands. Among them, $a$ stands are connected to the terminal by boarding bridges, so passengers can board the plane directly through the bridge. The other $b$ stands are not connected to the terminal, so passengers must take a shuttle bus before boarding. Obviously, taking a shuttle bus is a very bad experience, so every passenger who takes a shuttle bus will generate “unhappiness”. Now you are given, for each flight, the number of passengers, the boarding time, and the departure time. A plane must choose an available stand at its boarding time; at this time all passengers finish boarding, and then the plane will stay at that stand until its departure time. If a plane departs at time $x$, then at time $x$ the stand where it was parked becomes available. The airport management wants to minimize passengers’ unhappiness. To do this, a plane may change stands between its boarding time and departure time. Suppose a plane starts switching from stand A to stand B at time $x$. Then stand A is available at time $x+1$. Such a switch is possible if and only if stand B is available at time $x+1$.

The input contains multiple test cases. The first line contains a positive integer $T$ representing the number of test cases. For each test case: The first line contains three non-negative integers $n,a,b$, representing the number of planes, the number of stands with boarding bridges, and the number of stands without boarding bridges. The second line contains a floating-point number $p$, given with at most two digits after the decimal point. The next $n$ lines each contain three positive integers $x,s,t$, describing a plane’s number of passengers, boarding time, and departure time.

For each test case, output one line with one integer, representing the minimum unhappiness. If it is impossible to arrange a valid plan so that all planes can complete boarding, output `impossible`.

The problem statement seems not to give an explicit formula for unhappiness. From the sample explanation, it can be inferred that: Unhappiness $=$ (total number of people who take the shuttle bus) $+ \left\lfloor p \times \text{(number of passengers on the plane for each stand switch)} \right\rfloor$, summed over all switches. #### Constraints $1\le T\le 8,1\le n\le 200,0\le p\le1,1\le x\le 10^5,1\le s\le t\le10^9$. #### Sample Explanation Planes are numbered starting from $1$. At time $1$, plane $1$ is assigned to boarding bridge A, and passengers start boarding. Currently, plane $1$ is at boarding bridge A. At time $2$, plane $2$ is assigned to boarding bridge B, and passengers start boarding. Currently, plane $1$ is at boarding bridge A, and plane $2$ is at boarding bridge B. At time $3$, plane $2$ switches to shuttle stand A. At this time, boarding bridge B is still unavailable. At time $4$, plane $1$ departs, plane $2$ arrives at shuttle stand A, plane $4$ is assigned to boarding bridge A, plane $3$ is assigned to boarding bridge B, and passengers of planes $4$ and $3$ start boarding. After boarding is completed, plane $4$ switches to shuttle stand B. At this time, neither boarding bridge A nor boarding bridge B is available. At time $5$, plane $3$ arrives at shuttle stand B, boarding bridge A becomes available, and plane $5$ is assigned to boarding bridge A and starts boarding. Currently: plane $5$ — boarding bridge A, plane $4$ — boarding bridge B, plane $3$ — shuttle stand B, plane $2$ — shuttle stand A. At time $7$, plane $2$ departs, and plane $6$ is assigned to shuttle stand A. The unhappiness is $7 = 1$ (passengers of plane $6$ take the shuttle bus) $+ 4\times 0.5$ (plane $2$ switches stands) $+ 8\times 0.5$ (plane $3$ switches stands). #### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017. Translated by ChatGPT 5