A Journey to Greece

Tim has wanted to visit Greece for a long time. He already bought his flights to and from Athens, and he made a list of the historical sites he wants to see, such as Olympia and Delphi. Recent politics made public transport in Greece complicated. To keep the citizens happy with their new government, many short bus and train lines were opened, and they carry people around their own neighbourhood, to work or to the doctor. At the same time the long distance trains that suit tourists were shut down because they cost too much. That is bad news for Tim, who really likes travelling by train. He had even bought the Greece Card for Public Conveyance (GCPC), which makes every train and bus free for him.

The figure above draws the first example. Tim's tour has length 18.

Tim still wants to make his trip, but changing between local buses and trains is slower than he expected, so he wants to know whether he can see every site inside the window his flights leave him. His schedule is tight. He does keep some emergency money, enough for a single ticket for a special Greek taxi service that carries you from any point in Greece to any other point in a fixed amount of time.

Assume Tim never waits at a station for the next bus or train. The journey starts and ends in Athens. Tim may pass a place several times, and he may pass through a place without stopping. The journey fits the schedule if the travel times plus the times he spends at the sites add up to at most $G$. He may use the taxi ticket at most once, at any moment of the journey, and that ride takes $T$ no matter where it starts and where it ends.

Decide whether Tim can see every site in time, and if he can, whether he needs the taxi ticket.

The first line contains five integers $N$, $P$, $M$, $G$ and $T$. Here $N$ is the number of places in Greece, $P$ is the number of sites Tim wants to visit, $M$ is the number of connections, $G$ is the total time Tim can spend in Greece, and $T$ is the time one taxi ride takes ($1 \le N \le 20000$, $1 \le P \le 15$, $1 \le M, G \le 10^5$, $1 \le T \le 500$).

Each of the next $P$ lines contains two integers $p_i$ and $t_i$. Here $p_i$ is a place Tim wants to visit and $t_i$ is the time he spends at that site ($0 \le p_i < N$, $1 \le t_i \le 500$). The places $p_i$ are distinct.

Each of the next $M$ lines describes one connection with three integers $s_i$, $d_i$ and $t_i$. Here $s_i$ and $d_i$ are the two ends of the connection and $t_i$ is the time it takes ($0 \le s_i, d_i < N$, $1 \le t_i \le 500$).

Every connection runs in both directions. Tim's journey starts and ends in Athens, which is always place 0.

Print one line. Print impossible if Tim cannot visit all sites in time, possible without taxi if he can visit them all without the taxi ticket, and possible with taxi if he needs the taxi ticket.