그리스 여행

팀은 오래전부터 그리스에 가 보고 싶었다. 아테네를 오가는 항공권은 이미 끊어 두었고, 올림피아와 델포이처럼 꼭 보고 싶은 유적지 목록도 만들었다. 그런데 최근 그리스의 정치 상황이 바뀌면서 대중교통이 복잡해졌다. 새 정부는 시민의 환심을 사려고 동네 안을 도는 짧은 버스와 기차 노선을 잔뜩 열었다. 사람들을 직장이나 병원까지 실어 나르는 노선이다. 반대로 관광객에게 딱 맞던 장거리 기차는 운영비가 너무 든다는 이유로 없앴다. 기차 여행을 좋아하는 팀에게는 나쁜 소식이다. 게다가 팀은 모든 기차와 버스를 공짜로 타는 그리스 대중교통 카드(GCPC)를 이미 사 두었다.

위 그림은 첫 번째 예제 입력을 그린 것이다. 팀의 여행 길이는 18이다.

좋아하던 노선이 사라졌어도 팀은 그리스를 돌아볼 생각이다. 다만 지역 버스와 기차를 갈아타는 여행이 생각보다 느려서, 항공권이 정해 준 기간 안에 유적지를 모두 볼 수 있을지 알고 싶다. 일정이 빠듯하다는 것은 팀도 안다. 대신 비상금이 조금 있어서 특별한 그리스 택시 승차권을 한 장 살 수 있다. 이 택시는 그리스 안의 어느 지점에서 어느 지점으로든 정해진 시간에 데려다준다.

편의상 팀은 정류장에서 다음 버스나 기차를 기다리지 않는다고 가정한다. 여행은 아테네에서 시작해 아테네에서 끝난다. 같은 장소를 여러 번 지나가도 되고, 멈추지 않고 지나쳐도 된다. 이동에 쓴 시간과 유적지에 머문 시간을 모두 더한 값이 $G$ 이하이면 여행이 일정 안에 들어간다. 택시 승차권은 여행 중 언제든 최대 한 번 쓸 수 있고, 출발지와 도착지가 어디든 그 이동에는 $T$의 시간이 든다.

팀이 유적지를 모두 볼 수 있는지, 볼 수 있다면 택시 승차권이 필요한지 판단하라.

첫째 줄에 다섯 정수 $N$, $P$, $M$, $G$, $T$가 주어진다. $N$은 그리스의 장소 수, $P$는 팀이 방문할 유적지 수, $M$은 연결 수, $G$는 팀이 그리스에서 쓸 수 있는 전체 시간, $T$는 택시가 한 번 이동하는 데 걸리는 시간이다 ($1 \le N \le 20000$, $1 \le P \le 15$, $1 \le M, G \le 10^5$, $1 \le T \le 500$).

다음 $P$개 줄에는 두 정수 $p_i$와 $t_i$가 주어진다. $p_i$는 팀이 방문할 장소이고, $t_i$는 그 유적지에 머무는 시간이다 ($0 \le p_i < N$, $1 \le t_i \le 500$). $p_i$는 서로 다르다.

다음 $M$개 줄에는 연결 하나를 나타내는 세 정수 $s_i$, $d_i$, $t_i$가 주어진다. $s_i$와 $d_i$는 연결의 양 끝 장소이고, $t_i$는 그 연결을 지나는 데 걸리는 시간이다 ($0 \le s_i, d_i < N$, $1 \le t_i \le 500$).

모든 연결은 양방향이다. 팀의 여행은 아테네에서 시작해 아테네에서 끝나며, 아테네는 항상 0번 장소이다.

한 줄을 출력한다. 팀이 시간 안에 모든 유적지를 볼 수 없으면 impossible을, 택시 승차권 없이 볼 수 있으면 possible without taxi를, 택시 승차권이 있어야 볼 수 있으면 possible with taxi를 출력한다.