#2403. 「THUPC 2017」机场 / Airport

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wjh

题目描述

飞机场有 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 开始编号

在时刻 1 1 号飞机安排到登机桥 A,乘客开始登机;目前 1 号飞机在登机桥 A。

在时刻 2 2 号飞机安排到登机桥 B,乘客开始登机;目前 1 号飞机在登机桥 A, 2 号飞机在登机桥 B。

在时刻 3 2 号飞机切换到摆渡车 A,此时登机桥 B 尚不可用。

在时刻 4 1 号飞机起飞, 2 号飞机到达摆渡车 A, 3 号飞机安排到登机桥 A, 4 号飞机安排到登机桥 B, 3 号和 4 号的乘客开始登机,登机完成之后 3 号飞机切换到摆渡车 B,此时登机桥 A 和登机桥 B 都不空闲。

在时刻 5 3 号飞机到达摆渡车 B,登机桥 A 变为可用, 5 号飞机安排到登机桥 A,开始登机;目前 5 号——登机桥 A, 4 号——登机桥 B, 3 号——摆渡车 B, 2 号——摆渡车 A。

在时刻 7 2 号飞机起飞, 6 号飞机安排到摆渡车 A。

不愉快度为 7= 1 6 号飞机乘客乘摆渡车) +4 \times 0.5 2 号飞机切换停机位) +8 \times 0.5 3 号飞机切换停机位)

数据范围与提示

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}