2015 German Collegiate Programming Contest (GCPC)

A Journey to Greece

For a long time Tim wanted to visit Greece. He has already purchased his flight to and from Athens. Tim has a list of historical sites he wants to visit, e.g., Olympia and Delphi. However, due to recent political events in Greece, the public transport has gotten a little complicated. To make the Greek happy and content with their new government, many short-range bus and train lines have been created. They shall take the citizens around in their neighborhoods, to work or to their doctor. At the same time, long-range trains that are perfect for tourists have been closed down as they are too expensive. This is bad for people like Tim, who really likes to travel by train. Moreover, he has already purchased the Greece' Card for Public Conveyance (GCPC) making all trains and buses free for him.

prb7706.gif Visual representation of the Sample Input: Tim's tour has length 18.

Despite his preferred railway lines being closed down, he still wants to make his travel trough Greece. But taking all these local bus and train connections is slower than expected, so he wants to know whether he can still visit all his favorite sites in the timeframe given by his flights. He knows his schedule will be tight, but he has some emergency money to buy a single ticket for a special Greek taxi service. It promises to bring you from any point in Greece to any other in a certain amount of time.

For simplicity we assume, that Tim does never have to wait for the next bus or train at a station. Tell Tim, whether he can still visit all sites and if so, whether he needs to use this taxi ticket.


The first line contains five integers n, p, m, g and t, where n denotes the number of places in Greece, p the number of sites Tim wants to visit, m the number of connections, g the total amount of time Tim can spend in Greece, and t the time the taxi ride takes (1n2 * 104, 1p15, 1m, g105, 1t500).

Then follow p lines, each with two integers pi and ti, specifying the places Tim wants to visit and the time Tim spends at each site (0pi < n, 1ti500). The sites pi are distinct from each other.

Then follow m lines, each describing one connection by three integers si, di and ti, where si and di specify the start and destination of the connection and ti the amount of time it takes (0si, di < n, 1ti500).

All connections are bi-directional. Tim’s journey starts and ends in Athens, which is always the place 0.


Print either "impossible", if Tim cannot visit all sites in time, "possible without taxi", if he can visit all sites without his taxi ticket, or "possible with taxi", if he needs the taxi ticket.

Time limit 3 seconds
Memory limit 128 MiB
Input example #1
6 3 10 18 5
1 2
4 2
5 2
0 1 2
1 2 3
2 4 3
1 3 10
2 3 6
0 3 2
3 4 2
4 5 1
3 5 2
0 5 5
Output example #1
possible with taxi
Source 2015 German Collegiate Programming Contest (GCPC), June 20, Problem A