Problem Description

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$.

Input Format

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.

Output Format

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.

2
3 1 1
0.5
1 1 5
1 1 5
1 1 5
6 2 2
0.5
4 1 4
4 2 7
8 4 8
8 4 8
10 5 9
1 7 9

impossible
7

Hint

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