Oh Min-sik's Worry

Oh Min-sik travels between cities to sell goods. The country has N cities numbered from 0 to N-1, and his trip starts in city A and ends in city B.

There are several transportation routes he can use. Each route has a start city, an end city, and a cost. Every route can be used only in its given direction, and it may be used multiple times.

Each city has a fixed amount of money he earns whenever he visits it. If he visits the same city multiple times, he earns that amount every time.

Min-sik wants to maximize the amount of money he has when he arrives at city B. The maximum can be negative if transportation costs exceed the money earned. Compute the maximum amount of money he can have at the destination.

The first line contains the number of cities N, the start city A, the destination city B, and the number of transportation routes M.

Each of the next M lines contains one route in the form start end cost.

The last line contains N integers: the amount of money earned whenever visiting each city, from city 0 through city N-1.

N and M are at most 50. Each earning amount and route cost is a non-negative integer at most 1,000,000.

If city B cannot be reached, print gg.

If it is possible to arrive at city B with arbitrarily large money, print Gee.

Otherwise, print the maximum amount of money Min-sik can have when he arrives at city B.