Чарівна річка Карлутка =)#6742
Група з туристів подорожує вздовж річки Карлутка. Вони хочуть перетнути річку, але не знайшли міст. На щастя, у воді плавають купи сміття, і туристи вирішили спробувати перейти річку, стрибаючи з однієї купи на іншу.
Кожен турист може стрибнути до метрів у будь-якому напрямку за один стрибок. Один стрибок займає рівно одну секунду. Туристи знають, що річка має ширину метрів, і вони визначили координати куп сміття (X_i, Y_i) та місткість кожної купи (C_i, максимальна кількість туристів, яку ця купа може витримати одночасно). Купи сміття невеликі і можуть бути представлені як точки. Річка тече вздовж осі . Туристи починають на березі річки на по осі . Координата протилежного берега дорівнює .
Туристи хочуть дізнатися, чи зможуть вони дістатися до протилежного берега річки, і скільки часу це займе.
Перша строка введення містить чотири цілі числа: кількість куп сміття (0 \le N \le 50), кількість туристів (0 < M \le 50), максимальна довжина стрибка туриста (0 \le D \le 1000) та ширина річки (0 < W \le 1000). Наступні рядків описують купи сміття, кожен рядок складається з трьох цілих чисел: (0 < X_i < 1000, 0 < Y_i < W, 0 \le C_i \le 1000) — координати купи та її місткість.
Виведіть одне число, що вказує мінімальний час (у секундах), за який усі туристи зможуть перетнути річку, або рядок "IMPOSSIBLE", якщо перетнути річку неможливо.
Приклад 1