Yunanıstana Səyahət#7706
Tim çoxdan Yunanıstana səfər etməyi arzulayırdı. O, artıq Afina və geri dönüş üçün bilet alıb. Timin Olimpiya və Delfi kimi ziyarət etmək istədiyi tarixi yerlərin siyahısı var. Ancaq Yunanıstandakı son siyasi hadisələr səbəbindən ictimai nəqliyyat daha az əlverişli olmuşdur. Vətəndaşların yeni hökumətlərindən məmnun olmaları üçün avtobuslar və qatarlar üçün qısa məsafəli marşrutlar müəyyən edilmişdir. Onlar vətəndaşları işə və ya həkimə aparır. Lakin turistlər üçün əlverişli olan uzun məsafəli qatarlar bağlanmış, çünki onlar çox bahalıdır. Bu, qatarla səyahət etməyi sevən Tim kimi insanlar üçün səyahəti çətinləşdirir. Bundan əlavə, o, artıq Yunanıstan üçün turistik kart alıb ki, bu da ona bütün qatar və avtobusların pulsuz olmasını təmin edir.
Tim-in tur müddəti .
Dəmir yolu xətlərinin bağlanmasına baxmayaraq, Tim hələ də Yunanıstanda səyahət etmək istəyir. Yerli avtobus və qatar marşrutları kifayət qədər yavaş olsa da, ölkədə qalma müddətində sevimli yerlərini ziyarət edə biləcəyini öyrənmək istəyir. Onun cədvəli sıx olacaq, amma ölkənin istənilən nöqtəsindən istənilən digər nöqtəyə sabit müddətdə çatdıracaq Yunan taksi xidməti üçün vahid bileti almaq imkanı var.
Sadəlik üçün fərz edək ki, stansiyada növbəti avtobusu və ya qatarı gözləmək Tima heç vaxt lazım olmayacaq. Məlakə edin, Tim bütün yerləri ziyarət edə biləcəkmi və əgər bəli, taksi istifadə etmək lazım gələcəkmi.
Birinci sətir beş tam ədədi n, p, m, g və ehtiva edir, burada:
n~(1 \le n \le 2 \cdot 10^4) — Yunanıstanda olan yerlərin sayı,
p~(1 \le p \le 15) — Tim-in ziyarət etmək istədiyi yerlərin sayı,
m~(1 \le m \le 10^5) — nəqliyyat əlaqələrinin sayı,
g~(1 \le g \le 10^5) — Tim-in Yunanıstanda qalma müddəti,
t~(1 \le t \le 500) — taksiylə səyahət müddəti.
Növbəti sətir hər biri iki ədəd x_i və y_i~(0 \le x_i < n, 1 \le y_i \le 500) ehtiva edir — Tim-in ziyarət etmək istədiyi yer və ziyarət müddəti. Bütün x_i yerləri müxtəlifdir.
Növbəti sətir hər biri bir əlaqəni təsvir edir və üç ədəd s_i, d_i və w_i~(0 \le s_i, d_i < n, 1 \le w_i \le 500) ehtiva edir — başlanğıc və son yer, habelə aralarındakı hərəkət müddəti. Bütün əlaqələr ikitərəflidir. Tim-in səyahəti Afina, yer nömrəsi olan şəhərdə başlayır və bitir.
Üç mesajdan birini çıxarın:
impossible — əgər Tim ayrılan müddətdə bütün yerləri ziyarət edə bilməyəcəksə;
possible without taxi — əgər o, taksi istifadə etmədən bütün yerləri ziyarət edə biləcəksə;
possible with taxi — əgər bütün yerləri ziyarət etmək üçün taksi xidmətindən istifadə etmək lazım gələcəksə.
Nümunə 1