题目描述

有 $M$ 名游客要横渡一条宽度为 $W$ 的河。河流沿 $x$ 轴方向，游客从 $y=0$ 的河岸出发，目标是到达 $y=W$ 的另一岸。

河中有 $N$ 个漂浮垃圾堆，第 $i$ 个位于 $(X_i,Y_i)$，在任意时刻最多能够同时承载 $C_i$ 名游客。垃圾堆视为点。

每名游客每秒可以跳一次，每次可以向任意方向移动不超过 $D$ 的距离。游客可以在河岸等待，也可以通过若干垃圾堆逐步前进。

求所有 $M$ 名游客都到达对岸所需的最短时间。如果无论如何都无法全部过河，输出 IMPOSSIBLE。

输入格式

第一行四个整数 $N,M,D,W$：

• $0\le N\le50$；
• $1\le M\le50$；
• $0\le D\le1000$；
• $1\le W\le1000$。

接下来 $N$ 行，每行三个整数 $X_i,Y_i,C_i$，表示一个垃圾堆的位置和容量，其中 $0\le X_i<1000$，$0<Y_i<W$，$0\le C_i\le1000$。

输出格式

若可以全部过河，输出最短时间（秒）；否则输出：

IMPOSSIBLE

样例

输入

3 10 3 7
0 2 2
4 2 2
2 4 3

输出

6