Semàfors P94613

En Jordi està desesperat amb els semàfors de París. I és que estan pensats per a gent ràpida i amb reflexos, ja que només estan uns pocs segons en verd abans de posar-se un altre cop en vermell. A més, tots els semàfors canvien de color al mateix temps.

En Jordi vol anar des de l’hotel, el punt 0, fins al lloc del SWERC, el punt 1. Per això, ha de creuar passos de vianants. Lògicament, només pot creuar un pas si el semàfor està verd. Sempre triga un segon per creuar cada pas. Donats tots els passos de vianants, i els segons que duren els semàfors en verd i en vermell, quin és el temps mínim per anar des del punt 0 fins al punt 1 si quan en Jordi surt els semàfors s’acaben de posar en verd?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb quatre enters n, m, v i r, que són respectivament el nombre de punts, el nombre de passos de vianants, els segons que duren els semàfors en verd, i els segons que duren en vermell. Segueixen m parells x y, indicant un pas de vianants (bidirecccional) entre x i y. Suposeu 2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 5n, que v i r estan entre 1 i 10⁴, x ≠ y, i que no hi ha parells x y repetits.

Sortida

Per a cada cas, escriviu el temps mínim per anar del punt 0 al punt 1. Sempre hi haurà alguna manera d’anar de 0 a 1.