Oh Min-sik's Worry

Time limit2sMemory limit128 MB

Summary
Find the maximum money achievable traveling from city A to city B using weighted directed edges and city rewards, detecting infinite gain via positive cycles.
Level

Medium7 of 10

Topics
Graph, Shortest path, Dynamic programming, DFS
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples6

  1. Example 1

    Input
    5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
0 0 0 0 0
    Expected output
    -32

  2. Example 2

    Input
    5 0 4 5
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10
    Expected output
    Gee

  3. Example 3

    Input
    3 0 2 3
0 1 10
1 0 10
2 1 10
1000 1000 47000
    Expected output
    gg

  4. Example 4

    Input
    2 0 1 2
0 1 1000
1 1 10
11 11
    Expected output
    Gee

  5. Example 5

    Input
    1 0 0 1
0 0 10
7
    Expected output
    7

  6. Example 6

    Input
    5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
8 10 20 1 100000
    Expected output
    99988