#P16982. [SGU438] The Glorious Karlutka River =)

[SGU438] The Glorious Karlutka River =)

题目描述

有 MM 名游客要横渡一条宽度为 WW 的河。河流沿 xx 轴方向,游客从 y=0y=0 的河岸出发,目标是到达 y=Wy=W 的另一岸。

河中有 NN 个漂浮垃圾堆,第 ii 个位于 (Xi,Yi)(X_i,Y_i),在任意时刻最多能够同时承载 CiC_i 名游客。垃圾堆视为点。

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

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

输入格式

第一行四个整数 N,M,D,WN,M,D,W:

  • 0≤N≤500\le N\le50;
  • 1≤M≤501\le M\le50;
  • 0≤D≤10000\le D\le1000;
  • 1≤W≤10001\le W\le1000。

接下来 NN 行,每行三个整数 Xi,Yi,CiX_i,Y_i,C_i,表示一个垃圾堆的位置和容量,其中 0≤Xi<10000\le X_i<1000,0<Yi<W0<Y_i<W,0≤Ci≤10000\le C_i\le1000。

输出格式

若可以全部过河,输出最短时间(秒);否则输出:

IMPOSSIBLE

样例

输入

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

输出

6