A Journey to Greece#7706
Tim has long dreamed of visiting Greece. He has already purchased tickets to and from Athens. Tim has a list of historical sites he wants to visit, such as Olympia and Delphi. However, due to recent political events in Greece, public transportation has become less convenient. To keep citizens satisfied with the new government, short-distance bus and train routes were established. They transport residents around their districts to work or to the doctor. At the same time, long-distance trains, which would be convenient for tourists, were closed because they are too expensive. This complicates travel for people like Tim, who enjoys traveling by train. Moreover, he has already purchased a Greek tourist card, which makes all trains and buses free for him.
The length of Tim's tour is .
Despite the closure of railway lines, Tim still wants to travel around Greece. Although local bus and train routes are quite slow, he wants to know whether he can visit all his favorite places during his stay in the country. His schedule will be tight, but he has the option to purchase a single ticket for the Greek taxi service, which can take him from any point in the country to any other in a fixed amount of time.
For simplicity, assume that Tim never has to wait for the next bus or train at a station. It is necessary to determine whether Tim can visit all the places, and if so, whether he will need to use the taxi.
The first line contains five integers n, p, m, g and , where
n~(1 \le n \le 2 \cdot 10^4) — the number of locations in Greece,
p~(1 \le p \le 15) — the number of places Tim wants to visit,
m~(1 \le m \le 10^5) — the number of transport connections,
g~(1 \le g \le 10^5) — the total time of Tim's stay in Greece,
t~(1 \le t \le 500) — the time for a taxi ride.
The next lines contain two integers x_i and y_i~(0 \le x_i < n, 1 \le y_i \le 500) — the place Tim wants to visit and the time spent there. All locations x_i are distinct.
Each of the next lines describes a single connection and contains three integers s_i, d_i and w_i~(0 \le s_i, d_i < n, 1 \le w_i \le 500) — the start and end locations, and the travel time between them. All connections are bidirectional. Tim's journey starts and ends in Athens, which is location number .
Print one of the following three messages:
impossible — if Tim cannot visit all locations within the allotted time;
possible without taxi — if he can visit all locations without using the taxi;
possible with taxi — if he needs to use the taxi service to visit all locations.
Example 1