题目描述

飞机场有 $a+b$ 个停机位，其中 $a$ 个停机位有登机桥连接飞机和候机厅，乘客可以通过登机桥直接由候机厅登上飞机；另外 $b$ 个停机位没有登机桥和候机厅相连，所以乘客登机需要先搭乘摆渡车再登机。

毫无疑问，搭乘摆渡车的体验是非常差的，所以每位搭乘摆渡车的乘客都会产生不愉快度。

现在，给定每架飞机的乘客数量，登机时间和起飞时间；飞机需要在登机时间点选择一个空闲的停机位，在这个时间点内所有乘客会完成登机，然后飞机会一直停在该停机位，直到起飞时间；

若某飞机在时刻 $x$ 起飞，则在时刻 $x$ 该飞机所在的停机位是空闲的。

飞机场的管理层希望能够尽量减少乘客的不愉快度，为此飞机在登机时间到起飞时间之间，可以切换停机位；

假设某飞机从 $x$ 时间开始由停机位 A 切换到停机位 B，那么停机位 A 在 $x+1$ 时间是空闲的。能进行这样的切换当且仅当停机位 B 在 $x+1$ 时间是空闲的。

输入格式

输入有多组数据，第一行一个正整数 $T$ 表示数据组数；对于每组数据：

第一行输入三个非负整数 $n,a,b$，分别表示飞机数量、有登机桥的停机位数量、没有登机桥的停机位数量；

第二行一个浮点数 $p$，输入最多保留小数点后两位；

接下来 $n$ 行，每行三个正整数 $x,s,t$，描述一架飞机的乘客数量、登机时间和起飞时间。

输出格式

对于每组数据，输出一行一个整数，表示最小的不愉快度。

如果无法安排一个合理的方案使得所有飞机都完成登机，则输出 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

数据范围与提示

$1 \le T \le 8$

$1 \le n \le 200$

$0 \le p \le 1$

$1 \le x \le 100000; 1 \le s < t \le 10^{9}$