Yunanıstana Səyahət
Tim uzun müddətdir ki, Yunanıstana səfər etməyi arzulayırdı. O, artıq Afina üçün gediş-dönüş biletlərini alıb. Tim'in ziyarət etmək istədiyi bir sıra tarixi yerlər var, məsələn, Olimpiya və Delfi. Lakin Yunanıstanda son siyasi hadisələr səbəbindən ictimai nəqliyyat bir qədər çətinləşib. Yunanlar yeni hökumətlərindən məmnun qalmaq üçün qısa məsafəli avtobus və dəmir yolu marşrutları təşkil ediblər. Bu marşrutlar vətəndaşları işə və ya həkimə aparır. Eyni zamanda, turistlər üçün ideal olan uzun məsafəli qatarlar bağlanıb, çünki onlar çox bahalıdır. Bu, qatarla səyahət etməyi çox sevən Tim kimi insanlar üçün xoşagəlməzdir. Üstəlik, o, artıq Yunanıstanda sərnişin daşımaları üçün kart alıb ki, bu da onun üçün bütün qatarları və avtobusları pulsuz edir.
Tim'in turunun uzunluğu 18-dir.
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 hərəkətləri kifayət qədər yavaş olsa da, o, Yunanıstanda qalarkən bütün sevimli yerlərini ziyarət edə biləcəyini bilmək istəyir. Tim'in cədvəli sıx olacaq, lakin onun Yunanıstan taksi xidmətinə vahid bilet almaq üçün əlavə pulu var. Bu xidmət sizi Yunanıstanın istənilən nöqtəsindən digərinə müəyyən bir zaman intervalında aparmağı vəd edir.
Sadəlik üçün, heç vaxt stansiyada növbəti avtobus və ya qatarı gözləməli olmayacağınızı qəbul edəcəyik. Tim bütün yerləri ziyarət edə biləcəkmi və əgər belədirsə, bu taksi biletindən istifadə etməli olacaqmı?
Giriş Məlumatları
Birinci sətir beş tam ədəd n, p, m, g və t ehtiva edir, burada n - Yunanıstandakı yerlərin sayı, p - Tim'in ziyarət etmək istədiyi yerlərin sayı, m - əlaqələrin sayı, g - Yunanıstanda keçirəcəyi ümumi vaxt və t - taksi ilə səyahət vaxtı (1 ≤ n ≤ 2 * 10^4, 1 ≤ p ≤ 15, 1 ≤ m, g ≤ 10^5, 1 ≤ t ≤ 500).
Növbəti p sətirin hər biri iki ədəd p[i] və t[i] (0 ≤ p[i] < n, 1 ≤ t[i] ≤ 500) ehtiva edir - Tim'in ziyarət etmək istədiyi yer və bu yerin ziyarət vaxtı. Bütün p[i] yerləri fərqlidir.
Növbəti m sətirin hər biri bir əlaqəni təsvir edir və üç ədəd s[i], d[i] və t[i] (0 ≤ s[i], d[i] < n, 1 ≤ t[i] ≤ 500) ehtiva edir, burada s[i] və d[i] başlanğıc və son yeri, t[i] isə yerlər arasında hərəkət vaxtını göstərir.
Bütün əlaqələr ikitərəflidir. Tim'in səyahəti Afinada - 0 nömrəli şəhərdə başlayır və bitir.
Çıxış Məlumatları
Əgər Tim ayrılan vaxtda bütün yerləri ziyarət edə bilməzsə, "impossible", əgər yerləri taksi biletindən istifadə etmədən ziyarət edə bilərsə, "possible without taxi", əgər bütün yerləri ziyarət etmək üçün taksi xidmətindən istifadə etməlidirsə, "possible with taxi" yazın.