Joyride

7월의 어느 멋진 화창한 날, 당신은 어린 딸 Joy와 함께 하루를 보내기로 했다. Joy는 옆 동네의 동화 공원을 아주 좋아하기 때문에, 당신은 그곳에서 하루를 보내기로 결정했다. 아내(안타깝게도 일을 해야 한다)는 당신을 공원까지 태워다 주고 다시 데려오기로 했다. 그런데 아내는 시간을 아주 엄격하게 지키는 사람이라, 공원 정문 앞에 당신을 데리러 올 정확한 시각을 알려 주었고 당신은 바로 그 시각에 그곳에 있어야 한다. 밖에서 기다리고 싶지도 않다. 그러면 어린 딸이 슬퍼할 테니까. 공원에서 더 많은 시간을 보낼 수 있었을 테니 말이다.

이제 공원에서의 체류를 계획해야 한다. 언제 도착하고 언제 떠나야 하는지는 알고 있다. 공원은 여러 놀이기구로 이루어져 있고, 작은 보도로 서로 연결되어 있다. 공원 입장은 무료지만, 공원의 모든 놀이기구를 한 번 이용할 때마다 요금을 내야 한다. Joy가 가장 좋아하는 공원이므로, 각 놀이기구를 이용하는 데 걸리는 시간과 각 놀이기구의 요금을 이미 알고 있다. 공원을 걸어 다닐 때, 놀이기구를 지나치면서 그냥 지나칠 수는 없다. Joy가 이미 그 놀이기구를 이용했더라도 마찬가지다. 그렇게 하면 Joy가 매우 슬퍼할 것이다. Joy는 공원을 아주 좋아하기 때문에 기꺼이 놀이기구를 두 번 이상 이용한다. 두 놀이기구 사이를 걷는 데는 주어진 시간이 걸린다.

알뜰한 부모인 당신은 공원에 있는 동안 가능한 한 적게 쓰고 싶다. 최소한 얼마가 필요한지 계산할 수 있겠는가?

입력은 다음과 같이 주어진다:

• 한 줄에 정수 x (1 ≤ x ≤ 1 000). 이는 도착한 시각과 픽업될 시각 사이의 시간(분)이다.

• 한 줄에 세 정수 n, m, t. 여기서

  • n (1 ≤ n ≤ 1 000)은 공원의 놀이기구 수이다.
  • m (1 ≤ m ≤ 1 000)은 보도의 수이다.
  • t (1 ≤ t ≤ 1 000)는 한 놀이기구에서 다른 놀이기구로 보도를 지나는 데 필요한 분 수이다.

• m개의 줄이 각각 두 정수 a와 b (1 ≤ a, b ≤ n)를 포함하며, 놀이기구 a와 b 사이에 보도가 있음을 나타낸다.

• n개의 줄이 각각 두 정수 t와 p (1 ≤ t, p ≤ 10^6)를 포함하며, 해당 놀이기구를 이용하는 데 t분이 걸리고 요금이 p유로임을 나타낸다.

당신은 항상 놀이기구 1에서 시작하고 체류가 끝나면 놀이기구 1로 돌아와야 한다. 입구가 그곳에 있기 때문이다. 즉, 놀이기구 1을 적어도 두 번(입장할 때 한 번, 퇴장할 때 한 번) 이용해야 한다. 놀이기구에 도착했다면 그 놀이기구를 두 번 이상 이용할 수 있다.

공원에서 x분 동안 체류하는 데 필요한 최소 금액을 정수 하나로 출력하거나, 정확히 x분 동안 체류하는 것이 불가능하면 It is a trap. (마침표 포함)를 출력한다.