You are given a set of cities, for each you know the anticipated excitement you get by visiting this city. You are also given a set birectional flights, and you need to choose 4 distinct cities A, B, C, D so there are direct flights between A-B, B-C, C-D and total excitement is maximized.

Example,

Input:

N cities:
New York 10000
San Francisco 1000
Texas 500
LA 20000
Chicago 3000
San Jose 900

M flights:
New York <-> San Francisco
New York <-> LA
Chicago <-> LA
San Jose <-> San Francisco

Output:

San Francisco -> New York -> LA -> Chicago
1000 + 10000 + 20000 + 3000 = 34000