오민식의 고민

오민식은 물건을 팔기 위해 여러 도시를 이동한다. 이 나라에는 0번부터 N-1번까지 번호가 붙은 N개의 도시가 있고, 여행은 시작 도시 A에서 출발해 도착 도시 B에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 개이며, 각 교통수단은 출발 도시, 도착 도시, 이용 비용이 정해져 있다. 모든 교통수단은 주어진 방향으로만 이용할 수 있고, 같은 교통수단을 여러 번 이용해도 된다.

각 도시에는 방문할 때마다 벌 수 있는 금액이 정해져 있다. 같은 도시를 여러 번 방문하면 그때마다 다시 돈을 번다.

오민식은 도착 도시 B에 도착했을 때 가지고 있는 돈을 최대화하려고 한다. 교통비가 번 돈보다 크면 최댓값이 음수가 될 수도 있다. 도착 도시에서 가질 수 있는 돈의 최댓값을 구하시오.

첫째 줄에 도시의 수 N, 시작 도시 A, 도착 도시 B, 교통수단의 개수 M이 주어진다.

다음 M개의 줄에는 교통수단 정보가 시작 끝 가격 형식으로 주어진다.

마지막 줄에는 0번 도시부터 N-1번 도시까지, 각 도시를 방문할 때마다 벌 수 있는 금액이 차례대로 주어진다.

N과 M은 50 이하이다. 도시에서 벌 수 있는 금액과 교통수단의 가격은 1,000,000 이하의 음이 아닌 정수이다.

도착 도시 B에 도착할 수 없다면 gg를 출력한다.

도착 도시 B에 도착하면서 가질 수 있는 돈을 무한히 크게 만들 수 있다면 Gee를 출력한다.

그 외에는 도착 도시 B에 도착했을 때 가질 수 있는 돈의 최댓값을 출력한다.